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.

&nbsp;
Example 1:

Input: s = "level"
Output: "l"
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".


Example 2:

Input: s = "ababab"
Output: "abab"
Explanation: "abab" is the largest prefix which is also suffix. They can overlap in the original string.


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 105
	s contains only lowercase English letters.


class Solution:
    def longestPrefix(self, s: str) -> str:
        n=len(s)
        lps=[0]*n
        j=0
        for i in range(1,n):
            while s[i]!=s[j] and j>0:
                j=lps[j-1]

            if s[i]==s[j]:
                lps[i]=j+1
                j+=1

        return s[:lps[-1]]
class Solution {
    public String longestPrefix(String s) {
       int n=s.length();
        char arr[] = s.toCharArray();
        int lps[]=new int[n];
        for(int i=1; i<n; i++){
            int j=lps[i-1]; // COMPARING ITS i WITH ITS PREV ELEMENT
            while(j>0 && arr[j]!=arr[i]){
                j=lps[j-1]; // DEACREASING TILL WE FIND ITS PREFIX WHICH IS EQUAL TO ITS SUFFIX
            }
            if(arr[j]==arr[i]){// IF ITS PREV IS SAME AS CURRENT THEN INCREAMENT IT
                j++;
            }
            lps[i]=j; // SAVE WHATEVER THE VALUE IS
        }
        int j=lps[n-1];
       StringBuilder sb = new StringBuilder();
        for(int i=0;i<j;i++){
            sb.append(arr[i]);
        }
        return sb.toString();

    }
}
/*
 ALTERNATE

  for(int i=1;i<n;i++){
            if(arr[i]==arr[j]){ // IF SAME INCREASE IT
                lps[i]=++j;
            }else if(j>0){ // ELSE DEACREASE TILL WE ARE NOT FINDING IT
                j=lps[j-1];
                i--;
            }
        }
        return s.substring(0,j);

 */
class Solution {
public:
    string longestPrefix(string s) {
        if(s == "")
            return "";
        int n = s.length();
        int arr[n];
        fill(arr, arr + n, 0);
        int prevLPS = 0, i = 1;
        while(i < n){
            if(s[i] == s[prevLPS]){
                arr[i] = prevLPS + 1;
                i++;
                prevLPS++;
            }
            else if(prevLPS == 0){
                arr[i] = 0;
                i++;
            }
            else{
                prevLPS = arr[prevLPS - 1];
            }
        }
        int oplen = arr[n-1];
        string temp = s.substr(n - oplen, oplen);
        return temp;
    }
};
var longestPrefix = function(s) {
    const len = s.length;
    const z = new Array(len).fill(0);
    let l = 0, r = 0;
    
    for(let i = 1; i < len; i++) {
        if(i <= r) 
            z[i] = Math.min(r - i + 1, z[i - l]);
        while(i + z[i] < len && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        if(i + z[i] - 1 > r) {
            r = i + z[i] - 1;
            l = i;
        }
    }
    
    let idx = -1;
    for(let i = 1; i < len; i++) {
        if(i + z[i] == len) {
            idx = i;
            break;
        }
    }
    if(idx == -1) return '';
    return s.slice(idx);
};
Longest Happy Prefix