---
Difficulty: Hard
Source: 160 Days of Problem Solving
Tags:
  - Strings
---

# 🚀 _5. Longest Prefix Suffix_ 🧠

The problem can be found at the following link: [Problem Link](https://www.geeksforgeeks.org/batch/gfg-160-problems/track/string-bonus-problems/problem/longest-prefix-suffix2527)

## 💡 **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)

```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)

```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)

```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](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Let’s make this learning journey more collaborative!

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

---

<div align="center">
  <h3><b>📍Visitor Count</b></h3>
</div>

<p align="center">
  <img src="https://visitor-badge.laobi.icu/badge?page_id=Hunterdii.GeeksforGeeks-POTD" />
</p>