A-Good String: Codeforces 1385 D: Explained

This is another editorial post of the code forces problem a-Good String.

Detailed Editorial

In this problem our task is to find the minimum number of moves required to obtain a-good string from the given string.

Length of the given string is in form 2^k where (k ≥ 0) and according to the problem, a-good string has some conditions –

  • The length of s is 1, and it consists of the character c (s[1] = c).
  • The length of s is greater than 1, the first half of the string consists of only the character c ( s[1] = s[2] = ⋯ = s[n/2]= c) and the second half of the string (the string s[n/2+1] = s[n/2+2] … s[n]) is a (c+1) – good string.
  • The length of s is greater than 1, the second half of the string consists of only the character c ( s[1] = s[2] = ⋯ = s[n/2]= c) and the first half of the string (the string s[n/2+1] = s[n/2+2] … s[n]) is a (c+1) – good string.

Also it is written clearly in the problem that c-good string will start with c = ‘a’, so basically if string is ‘xxyy’, the minimum number of moves to obtain a good string is 4 (‘aabc’).

Hope you understood the problem statement very well, if not read it again and understand it clearly still have some difficulty in understanding the problem, ask it in comments.

This problem can be solved by Divide and Conquer approach.

First we have to divide the string into two halves and we have to check in both the parts to calculate minimum number of moves require to convert the first half of the string consists which contains only the character c.

We will recursively call the same function for the rest half of the string, we will convert it in same manner until the length of string is 1.

Let’s understand it by an example,

This is how we will write the recursive function. The overall complexity with be O(n log n).

Hope you got the intuition behind this problem, if any further doubts are there, ask in comments section.

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ull unsigned long long
#define ld long double
 
#define mod 1000000007
 
ll same(string &str, ll l, ll r, char ch)
{
    if(l == r) 
    {
        if(str[r] == ch) return 0;
        return 1;
    }
    
    ll mid = (l+r)/2;
    
    return same(str, l, mid, ch) + same(str, mid+1, r, ch);
}
 
ll F(string &str, ll l, ll r, char ch)
{
    if(l == r)
    {
        if(str[r] == ch) return 0;
        return 1;
    }
    
    ll mid = (l+r)/2;
    
    return min(same(str, l, mid, ch) + F(str, mid+1, r, ch+1), 
               F(str, l, mid, ch+1) + same(str, mid+1, r, ch));
}
 
int32_t main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    
    ll t = 1;
    cin >> t;
    
    while(t--)
    {
        ll n;
        cin >> n;
        
        string str;
        cin >> str;
        
        cout<<F(str, 0, n-1, 'a')<<"\n";
    }
    return 0;
}

Leave a Comment

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