Minimum number of times A has to be repeated such that B is a substring of it

Last Updated : 01 Mar, 2023

Given two strings A and B. The task is to find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution exists, print -1.

Examples:

Input : A = “abcd”, B = “cdabcdab”
Output : 3
Repeating A three times (“abcdabcdabcd”), B is a substring of it. B is not a substring of A when it is repeated less than 3 times.

Input : A = “ab”, B = “cab”
Output : -1

Approach :
Imagine we wrote S = A+A+A+… If B is a substring of S, we only need to check whether some index 0 or 1 or …. length(A) -1 starts with B, as S is long enough to contain B, and S has a period of length(A).
Now, suppose ans is the least number for which length(B) <= length(A * ans). We only need to check whether B is a substring of A * ans or A * (ans+1). If we try k < ans, then B has a larger length than A * ans and therefore can’t be a substring. When k = ans+1, A * k is already big enough to try all positions for B( A[i:i+length(B)] == B for i = 0, 1, …, length(A) – 1).

Below is the implementation of the above approach:

C

// C program to find Minimum number of times A 
// has to be repeated such that B is a substring of it
#include <stdio.h>
#include <string.h>
 
// Function to check if a number 
// is a substring of other or not
int issubstring(char* str2, char* rep1)
{
    int M = strlen(str2);
    int N = strlen(rep1);
 
    // Check for substring from starting 
    // from i'th index of main string
    for (int i = 0; i <= N - M; i++) {
        int j;
 
        // For current index i, 
        // check for pattern match
        for (j = 0; j < M; j++)
            if (rep1[i + j] != str2[j])
                break;
 
        if (j == M) // pattern matched
            return 1;
    }
 
    return 0; // not a substring
}
 
// Function to find Minimum number of times A 
// has to be repeated such that B is a substring of it
int Min_repetation(char* A, char* B)
{
    // To store minimum number of repetitions
    int ans = 1;
     
    // To store repeated string
    char *S = A;
     
    // Until size of S is less than B
    while(strlen(S) < strlen(B))
    {
        strcat(S, A);
        ans++;
    }
     
    // ans times repetition makes required answer
    if (issubstring(B, S)) return ans;
     
    char *temp=S;
    strcat(temp,A);
    // Add one more string of A   
    if (issubstring(B,temp)) 
        return ans + 1;
         
    // If no such solution exists    
    return -1;
}
 
// Driver code
int main()
{
    char A[] = "abcd", B[] = "cdabcdab";
     
    // Function call
    printf("%d", Min_repetation(A, B));
     
    return 0;
}

C++

// CPP program to find Minimum number of times A 
// has to be repeated such that B is a substring of it
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if a number 
// is a substring of other or not
bool issubstring(string str2, string rep1)
{
    int M = str2.length();
    int N = rep1.length();
 
    // Check for substring from starting 
    // from i'th index of main string
    for (int i = 0; i <= N - M; i++) {
        int j;
 
        // For current index i, 
        // check for pattern match
        for (j = 0; j < M; j++)
            if (rep1[i + j] != str2[j])
                break;
 
        if (j == M) // pattern matched
            return true;
    }
 
    return false; // not a substring
}
 
// Function to find Minimum number of times A 
// has to be repeated such that B is a substring of it
int Min_repetation(string A, string B)
{
    // To store minimum number of repetitions
    int ans = 1;
     
    // To store repeated string
    string S = A;
     
    // Until size of S is less than B
    while(S.size() < B.size())
    {
        S += A;
        ans++;
    }
     
    // ans times repetition makes required answer
    if (issubstring(B, S)) return ans;
     
    // Add one more string of A   
    if (issubstring(B, S+A)) 
        return ans + 1;
         
    // If no such solution exists    
    return -1;
}
 
// Driver code
int main()
{
    string A = "abcd", B = "cdabcdab";
     
    // Function call
    cout << Min_repetation(A, B);
     
    return 0;
}

Java

// Java program to find minimum number 
// of times 'A' has to be repeated 
// such that 'B' is a substring of it
class GFG 
{
 
// Function to check if a number 
// is a substring of other or not
static boolean issubstring(String str2, 
                           String rep1)
{
    int M = str2.length();
    int N = rep1.length();
 
    // Check for substring from starting 
    // from i'th index of main string
    for (int i = 0; i <= N - M; i++) 
    {
        int j;
 
        // For current index i, 
        // check for pattern match
        for (j = 0; j < M; j++)
            if (rep1.charAt(i + j) != str2.charAt(j))
                break;
 
        if (j == M) // pattern matched
            return true;
    }
 
    return false; // not a substring
}
 
// Function to find Minimum number 
// of times 'A' has to be repeated 
// such that 'B' is a substring of it
static int Min_repetation(String A, String B)
{
    // To store minimum number of repetitions
    int ans = 1;
     
    // To store repeated string
    String S = A;
     
    // Until size of S is less than B
    while(S.length() < B.length())
    {
        S += A;
        ans++;
    }
     
    // ans times repetition makes required answer
    if (issubstring(B, S)) return ans;
     
    // Add one more string of A 
    if (issubstring(B, S + A)) 
        return ans + 1;
         
    // If no such solution exists 
    return -1;
}
 
// Driver code
public static void main(String[] args) 
{
    String A = "abcd", B = "cdabcdab";
     
    // Function call
    System.out.println(Min_repetation(A, B));
}
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python3 program to find minimum number
# of times 'A' has to be repeated
# such that 'B' is a substring of it
 
# Method to find Minimum number 
# of times 'A' has to be repeated 
# such that 'B' is a substring of it
def min_repetitions(a, b):
    len_a = len(a)
    len_b = len(b)
     
    for i in range(0, len_a):
         
        if a[i] == b[0]:
            k = i
            count = 1
            for j in range(0, len_b):
                 
                # we are reiterating over A again and 
                # again for each value of B 
                # Resetting A pointer back to 0 as B 
                # is not empty yet
                if k >= len_a:
                    k = 0
                    count = count + 1
                     
                # Resetting A means count 
                # needs to be increased
                if a[k] != b[j]:
                    break
                k = k + 1
                 
            # k is iterating over A
            else:
                return count
    return -1
 
# Driver Code
A = 'abcd'
B = 'cdabcdab'
print(min_repetitions(A, B))
 
# This code is contributed by satycool

C#

// C# program to find minimum number 
// of times 'A' has to be repeated 
// such that 'B' is a substring of it
using System;
     
class GFG 
{
 
// Function to check if a number 
// is a substring of other or not
static Boolean issubstring(String str2, 
                           String rep1)
{
    int M = str2.Length;
    int N = rep1.Length;
 
    // Check for substring from starting 
    // from i'th index of main string
    for (int i = 0; i <= N - M; i++) 
    {
        int j;
 
        // For current index i, 
        // check for pattern match
        for (j = 0; j < M; j++)
            if (rep1[i + j] != str2[j])
                break;
 
        if (j == M) // pattern matched
            return true;
    }
 
    return false; // not a substring
}
 
// Function to find Minimum number 
// of times 'A' has to be repeated 
// such that 'B' is a substring of it
static int Min_repetation(String A, String B)
{
    // To store minimum number of repetitions
    int ans = 1;
     
    // To store repeated string
    String S = A;
     
    // Until size of S is less than B
    while(S.Length < B.Length)
    {
        S += A;
        ans++;
    }
     
    // ans times repetition makes required answer
    if (issubstring(B, S)) return ans;
     
    // Add one more string of A 
    if (issubstring(B, S + A)) 
        return ans + 1;
         
    // If no such solution exists 
    return -1;
}
 
// Driver code
public static void Main(String[] args) 
{
    String A = "abcd", B = "cdabcdab";
     
    // Function call
    Console.WriteLine(Min_repetation(A, B));
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Javascript program to find Minimum number of times A 
// has to be repeated such that B is a substring of it
 
// Function to check if a number 
// is a substring of other or not
function issubstring(str2, rep1)
{
    var M = str2.length;
    var N = rep1.length;
 
    // Check for substring from starting 
    // from i'th index of main string
    for (var i = 0; i <= N - M; i++) {
        var j;
 
        // For current index i, 
        // check for pattern match
        for (j = 0; j < M; j++)
            if (rep1[i + j] != str2[j])
                break;
 
        if (j == M) // pattern matched
            return true;
    }
 
    return false; // not a substring
}
 
// Function to find Minimum number of times A 
// has to be repeated such that B is a substring of it
function Min_repetation(A, B)
{
    // To store minimum number of repetitions
    var ans = 1;
     
    // To store repeated string
    var S = A;
     
    // Until size of S is less than B
    while(S.length < B.length)
    {
        S += A;
        ans++;
    }
     
    // ans times repetition makes required answer
    if (issubstring(B, S)) 
        return ans;
     
    // Add one more string of A   
    if (issubstring(B, S+A)) 
        return ans + 1;
         
    // If no such solution exists    
    return -1;
}
 
// Driver code
var A = "abcd", B = "cdabcdab";
 
// Function call
document.write( Min_repetation(A, B));
 
 
</script>

Output

Time Complexity: O(N * M)
Auxiliary Space: O(1).

Approach 2:

Idea here is to try and find the string using a brute force string searching algorithm (n * m). The only difference here is to calculate the modulus (i % n) when the counter reaches the end of the string.

Below is the implementation of the above approach:

C

#include <stdio.h>
#include <string.h>
 
int repeatedStringMatch(char* A, char* B)
{
    int m = strlen(A);
    int n = strlen(B);
 
    int count;
    int found = 0;
 
    for (int i = 0; i < m; i++) {
        int j = i;
        int k = 0;
        count = 1;
 
        while (k < n && A[j] == B[k]) {
            if (k == n - 1) {
                found = 1;
                break;
            }
            j = (j + 1) % m;
 
            if (j == 0)
                count++;
 
            k++;
        }
        if (found)
            return count;
    }
    return -1;
}
 
int main()
{
    char A[] = "abcd";
    char B[] = "cdabcdab";
 
    printf("%d",repeatedStringMatch(A, B));
    return 0;
}

C++

#include <bits/stdc++.h>
using namespace std;
 
int repeatedStringMatch(string A, string B)
{
    int m = A.length();
    int n = B.length();
 
    int count;
    bool found = false;
 
    for (int i = 0; i < m; i++) {
        int j = i;
        int k = 0;
        count = 1;
 
        while (k < n && A[j] == B[k]) {
            if (k == n - 1) {
                found = true;
                break;
            }
            j = (j + 1) % m;
 
            if (j == 0)
                count++;
 
            k++;
        }
        if (found)
            return count;
    }
    return -1;
}
int main()
{
    string A = "abcd";
    string B = "cdabcdab";
 
    cout << repeatedStringMatch(A, B);
    return 0;
}

Java

/*package whatever //do not write package name here */
 
import java.io.*;
 
class GFG {
    static int repeatedStringMatch(String A, String B)
    {
        int m = A.length();
        int n = B.length();
 
        int count;
        boolean found = false;
 
        for (int i = 0; i < m; ++i) {
            int j = i;
 
            int k = 0;
 
            count = 1;
 
            while (k < n && A.charAt(j) == B.charAt(k)) {
 
                if (k == n - 1) {
                    found = true;
                    break;
                }
 
                j = (j + 1) % m;
 
                // if j = 0, it means we have repeated the
                // string
                if (j == 0)
                    ++count;
 
                k += 1;
            }
 
            if (found)
                return count;
        }
 
        return -1;
    }
    public static void main(String[] args)
    {
 
        String A = "abcd", B = "cdabcdab";
 
        // Function call
        System.out.println(repeatedStringMatch(A, B));
    }
}

Python

# Python implementation of this approach
def repeatedStringMatch(A, B):
 
    m = len(A)
    n = len(B)
 
    count = 0
    found = False
 
    for i in range(m):
        j = i
        k = 0
        count = 1
 
        while k < n and A[j] == B[k] : 
            if (k == n - 1) :
                found = True
                break
             
            j = (j + 1) % m
 
            if (j == 0):
                count = count + 1
 
            k = k + 1
         
        if (found):
            return count
    return -1
 
# Driver code
A = "abcd";
B = "cdabcdab";
 
print(repeatedStringMatch(A, B));
 
# This code is contributed by shinjanpatra

C#

// C# program to find minimum number
// of times 'A' has to be repeated
// such that 'B' is a substring of it
using System;
     
class GFG
{
static int repeatedStringMatch(string A, string B)
{
    int m = A.Length;
    int n = B.Length;
  
    int count;
    bool found = false;
  
    for (int i = 0; i < m; i++) {
        int j = i;
        int k = 0;
        count = 1;
  
        while (k < n && A[j] == B[k]) {
            if (k == n - 1) {
                found = true;
                break;
            }
            j = (j + 1) % m;
  
            if (j == 0)
                count++;
  
            k++;
        }
        if (found)
            return count;
    }
    return -1;
}
 
 
// Driver code
public static void Main(String[] args)
{
    String A = "abcd", B = "cdabcdab";
     
    // Function call
    Console.WriteLine(repeatedStringMatch(A, B));
}
}
 
// This code is contributed by Pushpesh Raj

Javascript

<script>
 
// JavaScript implementation of this approach
 
function repeatedStringMatch(A, B)
{
    let m = A.length;
    let n = B.length;
 
    let count;
    let found = false;
 
    for (let i = 0; i < m; i++) {
        let j = i;
        let k = 0;
        count = 1;
 
        while (k < n && A[j] == B[k]) {
            if (k == n - 1) {
                found = true;
                break;
            }
            j = (j + 1) % m;
 
            if (j == 0)
                count++;
 
            k++;
        }
        if (found)
            return count;
    }
    return -1;
}
 
// Driver code
let A = "abcd";
let B = "cdabcdab";
document.write(repeatedStringMatch(A, B));
 
</script>
 
// This code is contributed by shinjanpatra

Output

Time Complexity: O(N * M)

Auxiliary Space: O(1).

Suggest improvement

Maximize cost obtained by removal of substrings "pr" or "rp" from a given String

Check if the given string is vowel prime

Share your thoughts in the comments

Minimum number of times A has to be repeated such that B is a substring of it

C

C++

Java

Python3

C#

Javascript

C

C++

Java

Python

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?