Given a string s, return true if it can be built by repeating one of its non-empty substrings multiple times. Otherwise, return false.
Example 1
Input: s = "abab"
Output: true
Explanation: The substring "ab" repeated two times forms "abab".
Example 2
Input: s = "aba"
Output: false
Explanation: No smaller substring can be repeated to form "aba" exactly.
Approach
The important observation is this: If a string is made by repeating a smaller block, then some part of its beginning will also appear at the end. For example: s = "ababab"
The string is made by repeating "ab": ab + ab + ab Here, the prefix "abab" is also a suffix: prefix = "abab" suffix = "abab" This overlap happens because the same block keeps repeating. The KMP LPS array is useful here because it tells, for each position, the length of the longest proper prefix that is also a suffix. For the whole string, the last LPS value tells the largest overlap between the start and end of the string.
Suppose: n = length of string, longestBorder = last value of LPS array, blockLength = n - longestBorder
The blockLength is the smallest possible repeating block suggested by the prefix-suffix overlap. Now the final check is simple: n % blockLength == 0. If the string length is divisible by this block length, the smaller block can tile the whole string perfectly. If not, the overlap exists but it does not create a full repeated pattern.
Algorithm
Build the LPS array for the string. This is needed because LPS gives the longest prefix that also appears as a suffix, which is the main clue for repetition.
Look at the last value of the LPS array. This value represents the biggest overlap between the beginning and ending of the whole string.
If this overlap is
0, returnfalse. With no prefix-suffix overlap, there is no smaller repeated block that can form the string.Calculate
blockLength = n - longestBorder. This gives the size of the smallest block that could repeat to create the string.Check whether
nis divisible byblockLength. This is needed because a repeated block must fit into the string an exact number of times.Return
trueonly when the block fits perfectly. Otherwise, returnfalse.
Dry Run
Repeated Substring Pattern Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: /* * Builds the LPS array used by KMP to store * the longest prefix-suffix length at each index. */ vector<int> buildLPS(string pattern) { int n = pattern.size(); // lps[i] stores the longest proper prefix // that is also a suffix ending at index i. vector<int> lps(n, 0); // This stores the current matched prefix length. int length = 0; // Start from index 1 because lps[0] is always 0. int i = 1; while (i < n) { // If characters match, the current prefix match // can be extended by one character. if (pattern[i] == pattern[length]) { length++; lps[i] = length; i++; } // If there is a mismatch after some matched characters, // fall back to the previous possible prefix length. else if (length != 0) { length = lps[length - 1]; } // If no prefix match is left, this position // cannot extend any prefix-suffix match. else { lps[i] = 0; i++; } } return lps; }public: /* * Checks whether the string can be made by repeating * one smaller non-empty substring multiple times. */ bool repeatedSubstringPattern(string s) { int n = s.size(); // A single character cannot be formed // by repeating a smaller non-empty substring. if (n <= 1) { return false; } vector<int> lps = buildLPS(s); // This is the largest prefix of the whole string // that is also a suffix of the whole string. int longestBorder = lps[n - 1]; // Without any border, no repeating block // can cover both the start and the end. if (longestBorder == 0) { return false; } // This is the smallest block length suggested // by the prefix-suffix overlap. int blockLength = n - longestBorder; // The block must divide the string length exactly // to repeat without leaving extra characters. if (n % blockLength == 0) { return true; } // If the block does not fit exactly, // the string is not a repeated pattern. else { return false; } }};// Driver code startsint main() { string s = "abab"; Solution sol; cout << boolalpha << sol.repeatedSubstringPattern(s) << endl; return 0;}Complexity Analysis
Time Complexity: O(n), where n is the length of the string. The LPS array is built by scanning the string once.
Space Complexity: O(n), because the LPS array stores one value for each character.
Interview follow-up Questions
The LPS array shows how much of the start of the string also appears at the end. A repeated string naturally creates this kind of overlap, so the last LPS value gives a strong clue about the repeating block.
Be the first to add a comment.