Explorer
Data Structures & Algorithms

Find longest proper prefix that is also a suffix using KMP LPS.

Problem Statement

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.

Examples

Input: s = "level"

Output: "l"

Explanation: Combining the input according to Longest happy prefix logic yields "l".

Input: s = "ababab"

Output: "abab"

Explanation: Combining the input according to Longest happy prefix logic yields "abab".

Complexity

Time Complexity: O(N)

Space Complexity: O(N)

Hints

šŸ’” Hint 1: A happy prefix is a proper prefix that is also a suffix. šŸ’” Hint 2: By definition, LPS[n - 1] in the KMP preprocessing algorithm computes the length of the longest proper prefix that is also a suffix. šŸ’” Hint 3: Compute LPS for s and return s.slice(0, lps[n - 1]).

Editorial & Approach

Problem Overview & Intuition

The definition of a happy prefix coincides exactly with the Longest Prefix Suffix (LPS) value of the entire string s. Computing the LPS array via KMP takes O(N) time, and s.slice(0, lps[n - 1]) yields the answer.

Step-by-Step Approach

  1. Compute the LPS array for string s using KMP.
  2. Length of the longest prefix suffix is k = lps[s.length - 1].
  3. Return s.slice(0, k).

Optimal Implementation (JavaScript)

function longestPrefix(s) {
  const n = s.length;
  const lps = new Array(n).fill(0);
  let len = 0, i = 1;
  while (i < n) {
    if (s[i] === s[len]) {
      len++;
      lps[i] = len;
      i++;
    } else {
      if (len !== 0) len = lps[len - 1];
      else {
        lps[i] = 0;
        i++;
      }
    }
  }
  return s.slice(0, lps[n - 1]);
}

Complexity Analysis

Time Complexity O(N) ā€” linear LPS array computation.
Space Complexity O(N) ā€” LPS table.

Edge Cases & Corner Traps Handled

  • No happy prefix exists: returns "".
  • Periodic string "ababab": returns "abab".

Longest happy prefix

Hard
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 Scenarios
1Example 1
Input: s = "level"
Output: "l"
Explanation:

Combining the input according to Longest happy prefix logic yields "l".

2Example 2
Input: s = "ababab"
Output: "abab"
Explanation:

Combining the input according to Longest happy prefix logic yields "abab".

Editor
Loading Editor...
s =
"level"
Output:Click "Run" above to execute and verify your code here.
l