---
Difficulty: Medium
Source: 160 Days of Problem Solving
Tags:
- Searching
- Strings
- Pattern Searching
---
# ๐ _4. Minimum Repeats to Make Substring_ ๐ง
The problem can be found at the following link: [Problem Link](https://www.geeksforgeeks.org/batch/gfg-160-problems/track/string-bonus-problems/problem/minimum-times-a-has-to-be-repeated-such-that-b-is-a-substring-of-it--170645)
## ๐ก **Problem Description:**
Given two strings `s1` and `s2`, return the minimum number of times `s1` has to be repeated so that `s2` becomes a substring of the repeated `s1`. If `s2` cannot be a substring of any repeated version of `s1`, return `-1`.
## ๐ **Example Walkthrough:**
**Input:**
```
s1 = "ww", s2 = "www"
```
**Output:**
```
2
```
**Explanation:** Repeating `s1` two times ("wwww"), `s2` is a substring of it.
**Input:**
```
s1 = "abcd", s2 = "cdabcdab"
```
**Output:**
```
3
```
**Explanation:** Repeating `s1` three times ("abcdabcdabcd"), `s2` is a substring. Less than 3 repeats would not contain `s2`.
**Input:**
```
s1 = "ab", s2 = "cab"
```
**Output:**
```
-1
```
**Explanation:** No matter how many times `s1` is repeated, `s2` canโt be a substring.
### Constraints:
1 โค |s1|, |s2| โค 10^5
## ๐ฏ **My Approach:**
1. **Repeated Concatenation Check:**
- Initialize a repeated version of `s1` and keep appending `s1` to it until its length meets or exceeds `s2`โs length.
- After each append, check if `s2` becomes a substring of this extended `s1`.
- If it does, return the number of repetitions used.
2. **Pattern Matching with KMP Algorithm:**
- Use the KMP (Knuth-Morris-Pratt) algorithm to efficiently search for `s2` within the extended repeated string of `s1`.
- The `LPS` (Longest Prefix Suffix) array is computed for `s2` to enable efficient substring search.
3. **Edge Cases:**
- If `s1` is already a substring of `s2`, return the number of repetitions found.
- If no valid repetition count satisfies the substring condition, return `-1`.
## ๐ **Time and Auxiliary Space Complexity**
- **Expected Time Complexity:** O(n + m), where `n` is the length of `s1` and `m` is the length of `s2`. This is because the KMP algorithm requires linear time to find a substring.
- **Expected Auxiliary Space Complexity:** O(m), as we need additional space to store the `LPS` array for `s2`.
## ๐ **Solution Code**
## Code (C++)
```cpp
class Solution {
public:
int minRepeats(string s1, string s2) {
int repeat = 1;
string repeatedStr = s1;
while (repeatedStr.length() < s2.length()) {
repeatedStr += s1;
repeat++;
}
if (repeatedStr.find(s2) != string::npos)
return repeat;
repeatedStr += s1;
repeat++;
if (repeatedStr.find(s2) != string::npos)
return repeat;
return -1;
}
};
```
## Code (Java)
```java
class Solution {
static void computeLPSArray(String s, int[] lps) {
int len = 0, idx = 1;
lps[0] = 0;
while (idx < s.length()) {
if (s.charAt(idx) == s.charAt(len)) {
len++;
lps[idx] = len;
idx++;
} else {
if (len == 0) {
lps[idx] = 0;
idx++;
} else {
len = lps[len - 1];
}
}
}
}
static boolean KMPSearch(String txt, String pat, int[] lps, int rep) {
int n = txt.length(), m = pat.length();
int i = 0, j = 0;
while (i < n * rep) {
if (txt.charAt(i % n) == pat.charAt(j)) {
i++;
j++;
if (j == m) return true;
} else {
if (j != 0) j = lps[j - 1];
else i++;
}
}
return false;
}
static int minRepeats(String s1, String s2) {
int n = s1.length();
int m = s2.length();
int[] lps = new int[m];
computeLPSArray(s2, lps);
int x = (m + n - 1) / n;
if (KMPSearch(s1, s2, lps, x)) return x;
if (KMPSearch(s1, s2, lps, x + 1)) return x + 1;
return -1;
}
}
```
## Code (Python)
```python
class Solution:
def computeLPSArray(self, s):
lps = [0] * len(s)
len_ = 0
idx = 1
while idx < len(s):
if s[idx] == s[len_]:
len_ += 1
lps[idx] = len_
idx += 1
else:
if len_ == 0:
lps[idx] = 0
idx += 1
else:
len_ = lps[len_ - 1]
return lps
def KMPSearch(self, txt, pat, lps, rep):
n, m = len(txt), len(pat)
i = j = 0
while i < n * rep:
if txt[i % n] == pat[j]:
i += 1
j += 1
if j == m:
return True
else:
if j != 0:
j = lps[j - 1]
else:
i += 1
return False
def minRepeats(self, s1, s2):
n, m = len(s1), len(s2)
lps = self.computeLPSArray(s2)
x = (m + n - 1) // n
if self.KMPSearch(s1, s2, lps, x):
return x
if self.KMPSearch(s1, s2, lps, x + 1):
return x + 1
return -1
```
## ๐ฏ Contribution and Support:
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: [Any Questions](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Letโs make this learning journey more collaborative!
โญ If you find this helpful, please give this repository a star! โญ
---
๐Visitor Count
