Given a string of characters, find the length of the longest proper prefix which is also a proper suffix.
NOTE: Prefix and suffix can be overlapping but they should not be equal to the entire string.
Examples :
Input: str = "abab" Output: 2 Explanation: "ab" is the longest proper prefix and suffix.
Input: str = "aaaa" Output: 3 Explanation: "aaa" is the longest proper prefix and suffix.
Expected Time Complexity: O(|str|)
Expected Auxiliary Space: O(|str|)
Constraints:
1 ≤ |str| ≤ 106
str contains lower case English alphabets
Approach 01:
-
C++
-
Python
class Solution { public: int lps(string str) { int length = str.length(); vector<int> lpsArray(length, 0); // Array to store the length of the longest prefix-suffix for (int i = 1; i < length; i++) { int prefixIndex = lpsArray[i - 1]; // Get the value from the previous index while (prefixIndex > 0 && str[prefixIndex] != str[i]) { prefixIndex = lpsArray[prefixIndex - 1]; // Move back in the array } lpsArray[i] = prefixIndex + (str[prefixIndex] == str[i] ? 1 : 0); // Update the current index } return lpsArray[length - 1]; // Return the last value in the array as the result } };
class Solution: def lps(self, string): length = len(string) lpsArray = [0] * length # Array to store the length of the longest prefix-suffix for i in range(1, length): prefixIndex = lpsArray[i - 1] # Get the value from the previous index while prefixIndex > 0 and string[prefixIndex] != string[i]: prefixIndex = lpsArray[prefixIndex - 1] # Move back in the array lpsArray[i] = prefixIndex + int(string[prefixIndex] == string[i]) # Update the current index return lpsArray[-1] # Return the last value in the array as the result
Time Complexity
- Building the LPS Array:
The algorithm iterates through the string using an outer loop that runs \(O(n)\), where \(n\) is the length of the string. Within this loop, the inner while loop may run at most \(n\) times in total across all iterations due to the nature of the prefix-suffix comparisons, which means the overall complexity is \(O(n)\).
- Overall Time Complexity:
The overall time complexity is \(O(n)\) because each character in the string is processed a constant number of times.
Space Complexity
- Space for LPS Array:
The algorithm uses an array,
lpsArray
, of size \(n\) to store the length of the longest prefix-suffix for each index in the string. This results in a space complexity of \(O(n)\). - Overall Space Complexity:
The overall space complexity is \(O(n)\) due to the storage of the
lpsArray
.