> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/string/hard/1392.-longest-happy-prefix.md).

# 1392. Longest Happy Prefix

## Problem Statement

<br>

A string is called a **happy prefix** if is a **non-empty** prefix which is also a suffix (excluding itself).

Given a string `s`, return *the **longest happy prefix** of* `s`. Return an empty string `""` if no such prefix exists.

&#x20;

**Example 1:**

<pre><code><strong>Input: s = "level"
</strong><strong>Output: "l"
</strong><strong>Explanation: s contains 4 prefix excluding itself ("l", "le", "lev", "leve"), and suffix ("l", "el", "vel", "evel"). The largest prefix which is also suffix is given by "l".
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: s = "ababab"
</strong><strong>Output: "abab"
</strong><strong>Explanation: "abab" is the largest prefix which is also suffix. They can overlap in the original string.
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= s.length <= 105`
* `s` contains only lowercase English letters.

## Intuition

```
Approach : 
Apply KMP to find largest match of Suffix and Prefix
```

### Links

<https://leetcode.com/problems/longest-happy-prefix/description/>

### Video Links

### Approach 1:

```
KMP
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    string longestPrefix(string s) {
        vector<int> lps(s.size(), 0);
        int prev=0, i=1;

        while(i<s.size()){
            if(s[i] == s[prev]){
                lps[i] = prev + 1;
                prev++; i++;
            }
            else if(prev == 0){
                lps[i] = 0;
                i++;
            }
            else
                prev = lps[prev-1];
        }

        int last_val = lps.back();

        return s.substr(0, last_val);
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###