Help me in solving SWAPUNITE problem

help
,
1

My issue

Why this algo is failing
i am keeping the index of all character using map
ans then iterating in same characherter’s index to get min req swaps

My code

#include<bits/stdc++.h>
using namespace std;
// MAIN CODE HERE

int conti(vector<int>&idx)
{

int contig=1;
int ans=0;
 for (int i=0;i<idx.size();i++)
 {
    if (idx[i+1]-idx[i]==1)
    {
        contig++;
        ans=max(ans,contig);
      
    }
    else
    {
        contig=1;
    }
 }
 ans=max(ans,contig);
//  cout <<ans<<" "<<idx.size()<<" ";
 
 return idx.size()-ans;
}
void solve()
{
 string s;
 cin >>s;
 unordered_map<char,vector<int>>um1;
 for (int i=0;i<s.size();i++)
 {
    um1[s[i]].push_back(i);
 } 

 //
 int mins=s.size();

 int ans=INT_MAX;
 for (auto it : um1)
 {
    ans=min(ans,conti(it.second));
 }
 cout <<ans<<endl;




}
int main()
{
   int t;
   cin>>t;
   while (t--)
   {
   solve();
   }
   
}

Problem Link: Swap and Unite Practice Coding Problem - CodeChef

2

@prasoonkushwah
plzz refer my c++ code for better understanding of the logic

#include <bits/stdc++.h>
using namespace std;

int main() {
	// your code goes here
    int t;
    cin>>t;
    while(t--)
    {
        string s;
        cin>>s;
        map<char,int> mp;
        for(int i=0;i<s.size();i++)
        {
            mp[s[i]]++;
        }
        int ans=INT_MAX;
        for(auto x:mp)
        {
         map<char,int> mp1;   
            for(int i=0;i<x.second;i++)
            {
                mp1[s[i]]++;
            }
           ans=min(ans,x.second-mp1[x.first]);
           for(int i=x.second;i<s.size();i++)
           {
               mp1[s[i]]++;
               mp1[s[i-x.second]]--;
               ans=min(ans,x.second-mp1[x.first]);
           }
        }
        cout<<ans<<endl;
    }

}
3

This might resolve your query

1 Like
4

thankyou this really helped