Longest Happy Prefix

HARD

Description

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 <= 10⁵
s contains only lowercase English letters.

Approaches

Checkout 3 different approaches to solve Longest Happy Prefix. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

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 "".

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 Analysis

Time Complexity: 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 Complexity: 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.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Longest Happy Prefix. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Longest Happy Prefix

Patterns:

String MatchingRolling HashHash Function

Data Structures:

String