🚀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