# Convert a String that is Repetition of a Substring of Length K

Difficulty Level Medium
Frequently asked in Accenture Adobe American Express Databricks FreeCharge
Hash Hashing HashMap String

## Problem Statement

In the “Convert a String that is Repetition of a Substring of Length K” problem we have given a string “s” and an integer “k”. Write a program to check whether is it possible to convert it to a string that is the repetition of a substring with k characters.

## Input Format

The first line containing a string “s”.

The second line containing an integer value “k”.

## Output Format

Print “YES” if it is possible to convert it to a string that is the repetition of a substring with k characters. Otherwise, print “NO”.

## Constraints

• 1<=|s|<=10^6
• s[i] must be a lower case English alphabet

## Example

```abcdefabc
3```
`YES`

Explanation: Here we can replace “def” with “abc”. Then our updated string s is “abcabcabc”. Now, we can easily see if we concatenate abc three times then we get this string.

```acdaacda
2```
`NO`

Explanation: There is no substring of length 2, that can we replaced and formed a string such that we get it by concatenation of substring of length k.

## Algorithm

1. Traverse the string and Build a map that contains the frequency of substrings(0 to k-1, k to 2k-1, 2k to 3k-1 and so on) of length k.maps strings of length k.

2. If there are only two different substrings of length k and the count of one of the sub string is 1, then print “YES”.

Longest Substring Without Repeating Characters

3. Otherwise print “NO”.

## Implementation

### C++ program to Convert a String that is Repetition of a Substring of Length K

```#include<bits/stdc++.h>
using namespace std;

int main()
{
string s;
cin>>s;
int k;
cin>>k;
int n=s.length();
if(n%k!=0)
{
cout<<"NO"<<endl;
}
else
{
unordered_map<string, int> m;
for (int i=0; i<n; i+=k)
{
m[s.substr(i, k)]++;
}
if(m.size()==1)
{
cout<<"YES"<<endl;
}
else if(m.size()==2)
{
if(m.begin()->second==1 || m.begin()->second==(n/k-1))
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
}
else
{
cout<<"NO"<<endl;
}
}
return 0;
}```

### Java program to Convert a String that is Repetition of a Substring of Length K

```import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

class sum
{
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
String s = sr.next();
int k = sr.nextInt();
int n=s.length();
if(n%k!=0)
{
System.out.println("NO");
}
else
{
HashMap<String, Integer> m = new HashMap<>();
for(int i=0;i<n;i+=k)
{
String x = s.substring(i,i+k);
int temp = m.get(s.substring(i,i+k))==null? 0 : m.get(s.substring(i,i+k));
m.put(s.substring(i,i+k), temp+1);
}
if(m.size()==1)
{
System.out.println("YES");
}
else if(m.size()==2)
{
int flag=0;
for(Map.Entry<String, Integer> e : m.entrySet())
{
if(e.getValue()==1)
{
flag=1;
break;
}
}
if(flag==0)
{
System.out.println("NO");
}
else
{
System.out.println("YES");
}
}
else
{
System.out.println("NO");
}
}
}
}
```
`abcdabab`
`YES`

## Complexity Analysis to Convert a String that is Repetition of a Substring of Length K

### Time Complexity

O(n) where n is the size of the given string “s”. Here we simply form substring(0 to k-1, k to 2k-1, 2k to 3k-1 and so on) ok k length and count their frequency by using hash map. Here we do this in linear time.

### Space Complexity

O(n) where n is the size of the given string “s”. Here we use hash map for storing the count of the substring of length k.