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

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.

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions