Convert to a string that is repetition of a substring of k length - GeeksforGeeks

Convert to a string that is repetition of a substring of k length - GeeksforGeeks
Given a string, find if it is possible to convert it to a string that is repetition of substring with k characters. To convert, we can replace one substring of length k with k characters.

One observation is, length of string must be a multiple of k as we can replace only one substring.
The idea is declare a map mp which maps strings of length k to an integer denoting its count. So, if there are only two different sub-strings of length k in the map container and count of one of the sub-string is 1 then answer is true. Otherwise answer is false.

bool checkString(string str, long k)

{

    // Length of string must be a multiple of k

    int n = str.length();

    if (n%k != 0)

        return false;

 

    // Map to store strings of length k and their counts

    unordered_map<string, int> mp;

    for (int i=0; i<n; i+=k)

        mp[str.substr(i, k)]++;

 

    // If string is already a repition of k substrings,

    // return true.

    if (mp.size() == 1)

        return true;

 

    // If number of distinct substrings is not 2, then

    // not possible to replace a string.

    if (mp.size() != 2)

        return false;

 

    // One of the two distinct must appear exactly once.

    // Either the first entry appears once, or it appears

    // n/k-1 times to make other substring appear once.

    if ((mp.begin()->second == (n/k - 1)) ||

                    mp.begin()->second == 1)

       return true;

 

    return false;

}

Read full article from Convert to a string that is repetition of a substring of k length - GeeksforGeeks