1392. Longest Happy Prefix

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.

class Solution {
public:
    string longestPrefix(string s) {
        vector<int> dp(s.length(), 0);
        int j = 0;
        for(int i = 1; i < s.length(); i++) {
            while(j > 0 and s[i] != s[j]) {
                j = dp[j-1];
            }
            if(s[i] == s[j])
                dp[i] = ++j;
        }
        return s.substr(0,dp.back());
    }
};