Leetcode Problem 1392. Longest Happy Prefix

1392. Longest Happy Prefix

Leetcode Solutions

KMP Algorithm for Longest Happy Prefix

  1. Initialize an array lps of the same length as the input string s with all zeros. This array will hold the length of the longest proper prefix which is also a suffix for the substring s[0:i].
  2. Initialize variables len and i to 0. len will track the length of the current longest prefix that matches a suffix, and i will iterate through the string.
  3. Loop through the string starting from the second character.
  4. If s[i] is equal to s[len], increment len and assign lps[i] to len. Increment i.
  5. If s[i] is not equal to s[len], check if len is not zero, then update len to lps[len - 1]. Otherwise, if len is zero, assign lps[i] to zero and increment i.
  6. After the loop, the last element of the lps array will contain the length of the longest happy prefix.
  7. Return the substring of s from the beginning to the length indicated by the last element of the lps array.
UML Thumbnail

Rolling Hash for Longest Happy Prefix

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...