5. Longest Prefix Suffix.md

Difficulty	Source	Tags
Hard	160 Days of Problem Solving	Strings

🚀 5. Longest Prefix Suffix 🧠

The problem can be found at the following link: Problem Link

💡 Problem Description:

Given a string s, find the length of the longest prefix which is also a suffix.
Note: The prefix and suffix can be overlapping, but they should not be equal to the entire string.

🔍 Example Walkthrough:

Input:

s = "abab"

Output:

2

Explanation:
"ab" is the longest prefix and suffix.

Input:

s = "aabcdaabc"

Output:

4

Explanation:
The string "aabc" is the longest prefix and suffix.

Input:

s = "aaaa"

Output:

3

Explanation:
"aaa" is the longest prefix and suffix.

Constraints:

• $1 \leq s.size() \leq 10^6$
• The string s contains only lowercase English alphabets.

🎯 My Approach:

1. LPS Array (Longest Prefix Suffix):
   We will use an auxiliary array lps[] to store the length of the longest proper prefix which is also a suffix for each substring ending at index i. The idea is based on the Knuth-Morris-Pratt (KMP) string matching algorithm.

2. Traverse the String:

   • Start by initializing two variables:
     • len = 0 which tracks the length of the current longest prefix suffix.
     • i = 1 which is the current position in the string.
   • For each character at position i, if it matches the character at position len, it extends the current prefix-suffix, so we increment len and move to the next character.
   • If there’s a mismatch, instead of simply moving forward, we use the lps[len - 1] value to jump to a smaller possible prefix-suffix length, thus avoiding unnecessary comparisons.

3. Final Answer:
   The value at lps[n-1] (where n is the length of the string) gives the length of the longest proper prefix which is also a suffix.

🕒 Time and Auxiliary Space Complexity:

• Time Complexity:
  The algorithm runs in O(n) time, where n is the length of the string. This is because we traverse the string once while constructing the lps array.

• Space Complexity:
  The space complexity is O(n), as we need an auxiliary array lps[] of size n to store the prefix-suffix lengths.

📝 Solution Code

Code (Cpp)

class Solution {
public:
    int longestPrefixSuffix(string &s) {
        int n = s.length();
        vector<int> lps(n, 0);  

        int len = 0; 
        int i = 1;    

        while (i < n) {
            if (s[i] == s[len]) {
                len++;
                lps[i] = len;  
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];  
                } else {
                    lps[i] = 0;  
                    i++;
                }
            }
        }

        return lps[n - 1]; 
    }
};

Code (Java)

class Solution {
    int longestPrefixSuffix(String s) {
        int n = s.length();
        int[] lps = new int[n]; 
        int len = 0; 
        int i = 1; 
        while (i < n) {
            if (s.charAt(i) == s.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1]; 
                } else {
                    lps[i] = 0; 
                    i++;
                }
            }
        }
        return lps[n - 1];
    }
}

Code (Python)

class Solution:
    def longestPrefixSuffix(self, s: str) -> int:
        n = len(s)
        lps = [0] * n  

        len_ = 0  
        i = 1 

        while i < n:
            if s[i] == s[len_]:
                len_ += 1
                lps[i] = len_  
                i += 1
            else:
                if len_ != 0:
                    len_ = lps[len_ - 1]  
                else:
                    lps[i] = 0  
                    i += 1

        return lps[n - 1]  

🎯 Contribution and Support:

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count