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

0
73 ## 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

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;
}``````