How do you solve Longest Happy Prefix on LeetCode?

Longest Happy Prefix (LeetCode #1392) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Understanding the difference between prefixes and suffixes is crucial.

What is the brute force solution for Longest Happy Prefix?

The brute force approach for Longest Happy Prefix is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks every possible prefix and sees if it matches any suffix. This is straightforward but inefficient, as it involves a lot of repeated comparisons. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Longest Happy Prefix?

Longest Happy Prefix uses the following concepts: String, Rolling Hash, String Matching, Hash Function. The recommended patterns to study are: String Matching, Prefix Function.

What are the interview tips for Longest Happy Prefix?

Always clarify the problem requirements and constraints before diving into coding. Think about edge cases, such as very short strings or strings with no happy prefixes. Practice building the LPS array separately to get comfortable with the KMP algorithm.

What are common mistakes when solving Longest Happy Prefix?

Not considering the case where the prefix and suffix can overlap. Forgetting to exclude the entire string itself when checking for prefixes.

#1392

Longest Happy Prefix

Hard

StringRolling HashString MatchingHash FunctionString MatchingPrefix Function

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

Using the KMP (Knuth-Morris-Pratt) algorithm's prefix table, we can efficiently find the longest prefix that is also a suffix without redundant comparisons.

⚙️

Algorithm

3 steps

1Step 1: Create a prefix table (LPS array) that stores the length of the longest proper prefix which is also a suffix for every substring of s.
2Step 2: The last value in the LPS array gives the length of the longest happy prefix.
3Step 3: Return the substring of s from the start to the length found in the LPS array.

solution.py13 lines

1def longest_happy_prefix(s):
2    n = len(s)
3    lps = [0] * n
4    j = 0
5    for i in range(1, n):
6        while j > 0 and s[i] != s[j]:
7            j = lps[j - 1]
8        if s[i] == s[j]:
9            j += 1
10            lps[i] = j
11        else:
12            lps[i] = 0
13    return s[:lps[-1]]

ℹ

Complexity note: The time complexity is O(n) because we traverse the string once to build the LPS array. The space complexity is O(n) due to the storage of the LPS array.

1Understanding the difference between prefixes and suffixes is crucial.
2The KMP algorithm's LPS array is a powerful tool for efficiently solving string problems.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.