Longest Prefix Suffix - POTD | 22-Sep-2024

[MuhammadTausif]

Longest Prefix Suffix

Link

Difficulty: Hard

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

[MuhammadTausif]

Solved

def lps(self, str):
        # code here
        n = len(str)
        dp = [0]*(n)

        for i in range(1, n):
            j = dp[i-1]
            while j > 0 and str[j] != str[i]:
                j = dp[j-1]
            dp[i] = j + int(str[j] == str[i])
        return dp[-1]