Coding

Longest happy prefix

Asked at

Microsoft

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given a string s, return the longest happy prefix of s. A happy prefix is a string that is both a proper prefix and a proper suffix.

If no such prefix exists, return an empty string "".

Input: s = "ababab"

Output: "abab"

Explanation: "abab" is the longest prefix which is also suffix. They can overlap in the original string.

Input: s = "aaaa"

Output: "aaa"

Explanation: "aaa" is the longest prefix which is also a suffix in the string "aaaa".

Input: s = "abc"

1 <= s.length <= 104

cpp

class Solution{
  public:		
	string lps(string s) {
	
	}
};

java

class Solution {
    public String lps(String s) {
      
    }
}

python

class Solution:
    def lps(self, s: str) -> str:

javascript

class Solution {
    lps(s) {
   
    }
}

csharp

class Solution {
    public string Lps(string s) {

    }
}

func LPS(str string) string {
    // Implement your logic here
}

Stuck? Show a way to structure it+

01Build the prefix-function array.
02At each index, fall back through prior prefix lengths on mismatch.
03Extend the current border on a match.
04Read the final prefix value.
05Return that length from the start of the string.

Reference answer

Build the KMP prefix-function array pi, where pi[i] is the length of the longest proper prefix of s ending at i that is also a suffix of s[0 through i]. For each position, start with j = pi[i minus one]. While j is positive and s[i] differs from s[j], fall back to pi[j minus one]. If they match, increment j and store it in pi[i]. The final value pi[n minus one] is exactly the longest proper prefix of the full string that is also its suffix, so return s.substring(0, that length). For "ababab", the final value is 4 and the answer is "abab"; overlap is allowed. Time is O(n) because KMP fallbacks are amortized, and space is O(n) for pi. Comparing every prefix and suffix directly can be O(n squared).

Then expect these follow-ups

How can rolling hashes solve this probabilistically?
Tests: follow-up reasoning
What is the relation between pi and the Z-function?
Tests: follow-up reasoning

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question