Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Problem Statement
2.1.
Example
3.
Intuition
4.
Approach
5.
Program
5.1.
Example
6.
Complexity Analysis
7.
Key Takeaways
Last Updated: Mar 27, 2024

Minimum Repetitions of String A, to Generate String B as its Substring

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction 

In this blog, we will discuss a problem that will help you to enhance your knowledge in the field of data structures and algorithms and boost your problem-solving skills. The below discussion is about a problem related to string and substrings. 

A substring can be defined as a continuous sequence of characters within a string. The below problem statement will help you to understand the problem.

Problem Statement

Two strings ‘A’ and ‘B’ are given. Your task is to find the minimum number of times string ‘A’ needs to be repeated so that string ‘B’ can be found as its substring. If it is not possible to find string ‘B’ as ‘A’’s substring after repetitions, print -1.

Example

Input: A  = “abbcd”, B = “bbcda”
Output: 2
Explanation: Currently ‘B’ is not a substring of ‘A’, so we can repeat ‘A’ two times so that A becomes “abbcdabbcd”, where B can be found as its substring.

Input: A = “aba”, B = “ba”
Output: 1
Explanation: In only one repetition, 

A = “aba

where B can be found as its substring.

Note: We suggest you try this problem yourself, before going to the below solution.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Intuition

We need to observe the fact that string B can be obtained as a substring of a string generated by definite repetitions of A, or it cannot be obtained at all. 

The number of times A needs to be repeated can be calculated by division of the size of string B by the size of A, i.e.

count = M / N 

where count = number of repetitions, 

M = size of string B and 

N = size of string A

But we can have any suffix of the string A as the prefix of string B, and vice versa. So to balance either case, we need to increase the count of repetition of string A by two: one to include as the prefix and one to include as the suffix. Thus the maximum possible repetitions of A to find string B as a substring is

count = M / N + 2

Approach

As discussed above, the maximum possible repetitions of A to find string B as a substring is (M / N) + 2, but we are asked to find the minimum number of repetitions, so we can start checking with the minimum required repetitions, i.e., M / N, then we can increase the count of repetitions unless we find B as a substring. If this count exceeds M / N +2, then we can conclude that string B cannot be found as a substring of a string generated by the repetitions of string A.

The implementation of the above approach can be understood by the below program.

Program

// Program to find minimum repetitions of string A to find string B as its substring.
#include <iostream>

using namespace std;

// Function to find minimum repetitions.
int minRepetitions(string &A, string &B)
{
      // Storing the length of strings.
      int N = A.length(), M = B.length();

      // Variable to store count of string A and maximum allowed repetitions.
      int count = M / N, mCount = M / N + 2;

      // Temporary string to store the repetitions of string ‘A’.
      string tmp = "";

      for (int i = 0; i < count; i++)
            tmp += A;

      // Increasing the repetitions until ‘B’ is found as a substring.
      while (count <= mCount)
      {
            // Checking if B is present as a substring.
            if (tmp.find(B) != string::npos)
                  return count;

            // Repeating the number of A.
            tmp += A;

            // Increasing the actual count.
            count++;
      }

      // If not possible, returning -1 finally.
      return -1;
}

// Main Function.
int main()
{
      // Input the strings.
      string A, B;
      cin >> A >> B;

      // Storing the final answer.
      int ans = minRepetitions(A, B);

      // Final output.
      if (ans == -1)
            cout << "Not Possible";
      else
            cout << "Minimum Repetitions Required: " << ans;

      return 0;
}

Example

Input

abbwe
weabbwea

Output

Minimum Repetitions Required: 3

Also check out - Substr C++

Complexity Analysis

Time Complexity: O(M), where ‘M’ is the size of string B.

Explanation: The for loop used to generate the string ‘tmp’, is running for (M / N) times, where in each repetition, adding the string A to ‘tmp’ takes O(N) time. Also, the later while loop takes no more than O(M) time to process the repetitions.
So the total time taken by the program will be O(N x (M / N)) time which is equal to O(M) time.  


Auxiliary Space: O(M), where ‘M’ is the size of string B.

Explanation: The string ‘tmp’, used to store the repetitions of string A, stores N characters a total of (M / N) times, evaluating to O(M).

 

Also see, Morris Traversal for Inorder.and Rabin Karp Algorithm

Key Takeaways

The above blog discussed an interesting question that involves the concepts of strings and substrings. ‘Minimum repetitions of string A, to generate string B as its substring’ is also an important problem from the interview point of view, where you can be tested for such concepts instantaneously.
Check out this problem - Longest String Chain

If you want to learn more about such problems, head over to our library section for many such interesting blogs. Keep learning.

Happy Coding!

Previous article
Rearrange a Binary String as Alternate X and Y Occurrences
Next article
Find the longest proper prefix that is also a suffix
Live masterclass