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

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”.

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.