Convert a string that is repetition of a substring of length k

Given a string and legth k, write a function to check whether is it possible to convert it to a string that is repetation of substring with k characters. This can be explained in below example

Example 1

INPUT
s = "abcdefabc"
k = 3

OUTPUT
TRUE  //we can replace "def" wtih "abc"

Example 2

INPUT
s = "acdaacda"
k = 2

OUTPUT
FALSE  // There is no substring of length 2, taht can be replaced

Algorithm

1. Build a map which maps strings of length k to an integer denotin its count

2. If there are only two different sub strings of length k and count of one of the sub string is 1, then return TRUE

C++ Program

#include<bits/stdc++.h>
//For c++ compilitaion purpose
#include <tr1/unordered_map>

using namespace std::tr1;
using namespace std;
 

bool isSubStringRepeated(string s, int k)
{   
    //Finding the length of the given string
    int n = s.length();
    //Length of the string must be a multiple of k
    if (n%k != 0)
        return false;
    //Creating a map
    unordered_map<string, int> m;
    for (int i=0; i<n; i+=k)
        m[s.substr(i, k)]++;
    //If string is already a repetation
    if (m.size() == 1)
        return true;
    //If no of disticnt substring not equal to 2
    if (m.size() != 2)
        return false;
    //if count of one of the sub string is 1
    if ((m.begin()->second == (n/k - 1)) ||
                    m.begin()->second == 1)
       return true;
 
    return false;
}
 
int main()
{
    string s = "abcdefabc";
    int k = 3;
    if(isSubStringRepeated(s, k))
    {
        cout <<"TRUE"<<endl;
    }
    else
    {
         cout << "FALSE"<<endl;
    } 
    return 0;
}
Try It

 


Next > < Prev
Scroll to Top