Longest Prefix Suffix

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| ≤ 10⁶
str contains lower case English alphabets

Approach 01:

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.