Given two strings a and b, return the minimum number of times a must be repeated so that b becomes a substring of the repeated string.
If it is impossible, return -1.
Example 1
Input: a = "abcd", b = "cdabcdab"
Output: 3
Explanation: Repeating a three times gives "abcdabcdabcd". The string "cdabcdab" appears inside it, so the answer is 3.
Example 2
Input: a = "a", b = "aa"
Output: 2
Explanation: Repeating "a" twice gives "aa", which contains b.
Approach
The first important observation is about length. If b has length m and a has length n, then repeating a fewer than ceil(m / n) times cannot even create a string long enough to hold b. So the first useful number of repetitions is: ceil(length of b / length of a) But length alone is not enough.
For example, with a = "abcd" and b = "cdabcdab", the match starts from the middle of one copy of a and continues into the next copies. Because of this boundary crossing, one extra copy of a may be needed.
That gives the full search:
repeat
ajust enough to cover the length ofbcheck whether
bis already inside itif not, add one more copy of
acheck again
If b is still not present, adding more copies will only repeat the same cycle of characters again. No new kind of alignment will appear, so the answer is -1. For substring checking, KMP is used. KMP avoids restarting the pattern from the beginning after every mismatch, which keeps the search efficient and interview-friendly.
Algorithm
First, store the lengths of
aandbbecause the minimum number of repetitions depends directly on these lengths.Compute
repeatCount = ceil(len(b) / len(a)). This is the smallest number of copies that can possibly fitbby length.Build a repeated string using
repeatCountcopies ofa. This is checked first because the problem asks for the minimum number of repetitions.Use KMP to check whether
bis a substring of the repeated string. KMP is used so the substring search does not waste time rechecking the same matched characters.If
bis found, returnrepeatCountimmediately because this is the smallest possible count.Add one more copy of
aand check again. This extra copy handles cases wherebstarts near the end of one copy and finishes in the next.If
bis still not found, return-1because all future copies only repeat the same character cycle.
Dry Run
Repeated String Match Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: /* Builds the LPS array used by KMP to decide how far the pattern pointer should move back. */ vector<int> buildLPS(string& pattern) { int m = pattern.length(); // lps[i] stores the longest proper prefix // that is also a suffix for pattern[0..i]. vector<int> lps(m, 0); // This stores the current matched prefix-suffix length. int length = 0; // The first LPS value is always 0, // so the process starts from index 1. int index = 1; while (index < m) { // Matching characters extend the current // prefix-suffix length by one. if (pattern[index] == pattern[length]) { length++; lps[index] = length; index++; } else { // If a smaller prefix-suffix exists, // try that length before setting zero. if (length != 0) { length = lps[length - 1]; } else { // No prefix-suffix can be reused here, // so this LPS value remains zero. lps[index] = 0; index++; } } } return lps; } /* Checks whether pattern appears inside text using the KMP string matching algorithm. */ bool containsUsingKMP(string& text, string& pattern) { int n = text.length(); int m = pattern.length(); // An empty pattern is always found at the start. if (m == 0) { return true; } // A longer pattern cannot fit inside a shorter text. if (m > n) { return false; } // The LPS array helps skip repeated comparisons. vector<int> lps = buildLPS(pattern); // This pointer moves through the repeated string. int textIndex = 0; // This pointer moves through the pattern string. int patternIndex = 0; while (textIndex < n) { // Matching characters keep the current // substring candidate alive. if (text[textIndex] == pattern[patternIndex]) { textIndex++; patternIndex++; // Matching the full pattern means // it exists inside the repeated string. if (patternIndex == m) { return true; } } else { // If some pattern characters matched, // reuse the longest useful prefix. if (patternIndex != 0) { patternIndex = lps[patternIndex - 1]; } else { // No partial match exists, so move // forward in the repeated string. textIndex++; } } } return false; }public: /* Returns the minimum number of repetitions of a needed so that b becomes a substring. */ int repeatedStringMatch(string a, string b) { int n = a.length(); int m = b.length(); // This is the minimum count needed // just to make the repeated string long enough. int repeatCount = (m + n - 1) / n; // This stores a repeated form of a // that is large enough to possibly contain b. string repeated = ""; for (int i = 0; i < repeatCount; i++) {Complexity Analysis
Time Complexity: O(N + M), where N is the length of a and M is the length of b. The repeated string length is bounded by M + N, and KMP scans linearly.
Space Complexity: O(N + M), because the repeated string and the LPS array are stored.
Interview follow-up Questions
After enough copies are added to cover the length of b, the only missing case is when b starts near the end of one copy of a and finishes in the next copy. One extra copy gives space for that boundary-crossing match.
Be the first to add a comment.