Scale Engineer

Longest Happy Prefix

Hard
#1290Time: O(n^2), where n is the length of the string. The loop runs up to n-1 times. Inside the loop, `substring` creation and `equals` comparison both take O(len) time. In the worst case, this leads to a quadratic time complexity: Σ(len) for len from n-1 to 1.Space: O(n), where n is the length of the string. In each iteration, we create two new substrings. The maximum length of these substrings is n-1, so the space required is proportional to n.
Patterns
String MatchingRolling HashHash Function
Data structures
String

Prompt

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.

 

Constraints:

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly implements the problem definition. We check every possible proper prefix, from the longest to the shortest, and see if it matches the corresponding suffix of the same length. The first match we find is guaranteed to be the longest one.

Algorithm

  • Let n be the length of the input string s.
  • Iterate a variable len from n - 1 down to 1.
  • In each iteration, get the prefix s.substring(0, len).
  • Get the suffix s.substring(n - len).
  • If the prefix equals the suffix, return the prefix.
  • If the loop finishes, return an empty string "".

Walkthrough

The algorithm iterates through all possible lengths for a happy prefix, starting from the largest possible length n-1 down to 1, where n is the length of the string s.

In each iteration, for a given length len:

  • We extract the prefix of length len: s.substring(0, len).
  • We extract the suffix of length len: s.substring(n - len).
  • We compare these two substrings.

If they are identical, we have found the longest happy prefix, so we return it immediately. If the loop completes without finding any match, it means no happy prefix exists, and we return an empty string.

class Solution {    public String longestPrefix(String s) {        int n = s.length();        for (int len = n - 1; len > 0; len--) {            String prefix = s.substring(0, len);            String suffix = s.substring(n - len);            if (prefix.equals(suffix)) {                return prefix;            }        }        return "";    }}

Complexity

Time

O(n^2), where n is the length of the string. The loop runs up to n-1 times. Inside the loop, `substring` creation and `equals` comparison both take O(len) time. In the worst case, this leads to a quadratic time complexity: Σ(len) for len from n-1 to 1.

Space

O(n), where n is the length of the string. In each iteration, we create two new substrings. The maximum length of these substrings is n-1, so the space required is proportional to n.

Trade-offs

Pros

  • Simple to understand and implement.

  • Directly follows the problem definition.

Cons

  • Inefficient for large strings, likely to cause a 'Time Limit Exceeded' error on platforms with strict time limits.

  • Repeatedly creates new string objects, which can be memory-intensive.

Solutions

class Solution {private  long[] p;private  long[] h;public  String longestPrefix(String s) {    int base = 131;    int n = s.length();    p = new long[n + 10];    h = new long[n + 10];    p[0] = 1;    for (int i = 0; i < n; ++i) {      p[i + 1] = p[i] * base;      h[i + 1] = h[i] * base + s.charAt(i);    }    for (int l = n - 1; l > 0; --l) {      if (get(1, l) == get(n - l + 1, n)) {        return s.substring(0, l);      }    }    return "";  }private  long get(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem