Question Name:Shil and Lucky String

#include<iostream>
 using namespace std;
 #include<bits/stdc++.h>
 int has1[26],has2[26];
  int main()
   {
    int n;
      cin>>n;
        char ff[n+10],ss[n+10];
          for(int i=0;i<n/2;i++)
          {
              cin>>ff[i];
               has1[ff[i]-'a']++;
          }
            for(int i=0;i<n/2;i++)
            {
 
                  cin>>ss[i];
                  has2[ss[i]-'a']++;
            }
            sort(ff,ff+n/2);
              sort(ss,ss+n/2);
              //case 1
               int ans1=0,ans2=0,ans3=0;
              for(int i=0;i<26;i++)
              {
                  ans1+=abs(has1[i]-has2[i]);
                //    cout<<"i " <<i<<" " <<has1[i]<<" " <<has2[i]<<endl;
 
              }
              int i=0,j=0;
               while(i!=n/2  && j!=n/2)
               {
                   if(ff[i]<ss[j])
                   {
 
                        i++;
                         j++;
                   }
                   else
                    j++;
 
               }
               ans2=abs(j-i);
 
 
               i=0,j=0;
               while(i!=n/2  && j!=n/2)
               {
                   if(ss[i]<ff[j])
                   {
 
                        i++;
                         j++;
                   }
                   else
                    j++;
 
               }
 
            ans3=abs(j-i);
             // cout<<ans1<<" "<<ans2<<" "<<ans3<<endl;
            cout<<min(min(ans1/2,ans2),ans3);
        return 0;
  }

Problem Description

Shil is your new boss and he likes lucky strings very much. A string is called lucky if and only if each character from first half of the string can be paired to each character from second half of the string. AND:

In each pair, a character from the first half is strictly greater than a character from the second half OR
In each pair, a character from the first half is strictly lesser than a character from the second half OR
In each pair, a character from the first half is equal to character from the second half.
Each character should be used exactly once in pairing.

Your are given a string S. You want to change the minimum number of characters to make this string lucky so that you can gift it to your boss.

Note that each character in lucky string should be in lower case alphabet ( ‘a’ – ‘z’ ).

Input format:
The first line consists of an integer N. The second line consists of N lower case characters.

Output format:
Print minimum number of changes required to make given string lucky.

Constraints:
1 <= N <= 10^5
N will be an even integer.

  • Test Case 1

    Input (stdin)

    6
    aabbbb
    

    Expected Output

    1
  • Test Case 2

    Input (stdin)

    4
    nscl
    

    Expected Output

    0

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.