27. Longest Happy Prefix (imp)

Longest Prefix Suffix

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.

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.

Example 3:

Input: s = "leetcodeleet"
Output: "leet"

Example 4:

Input: s = "a"
Output: ""

Solution: (Brute Force)

Checking for all prefix which are present in suffix.

Solution: (Rolling hash)

Approach: Hash for string: For the string of i size, the hash is: s[0] * 26 ^ (i - 1) + s[1] * 26 ^ (i -2) + ... + s[i - 2] * 26 + s[i - 1].

Computing Prefix hash: we will multiply the previous value by 26 and add a new letter.

"a", hash[0]: a "ab", hash[1]: a*26 + b, or hash[0] * 26 + b "abc", hash[2]: a * 26 * 26 + b * 26 + c, or hash[1] *26 + c.

Computing Suffix hash: we add a new letter multiplied by 26 ^ (i - 1)

class Solution
{
public:
    string longestPrefix(string s)
    {

        int m = 1000000000 + 7;
        int n = s.length();

        long long int prefix = 0;
        long long int suffix = 0;
        int len = 0;
        long long int h = 1;
        
        for (int i = 0; i < n - 1; i++)
        {

            int first = s[i] - 96;
            int last = s[n - i - 1] - 96;
            prefix = (prefix * 26 + first) % m;
            suffix = (suffix + last * h) % m;
            h = (h * 26) % m;

            if (prefix == suffix)
            {
                len = i + 1;
            }
        }

        return s.substr(0, len);
    }
};

Time Complexity: O(n)