Home » Technical Interview Questions » String Interview Questions » Convert a string that is repetition of a substring of length k

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



String

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

READ  Repeated Substring Pattern

 

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

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup