Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Longest Happy Prefix

HARDProblemSolveExternal Links

Description

A string is called a happy prefix if it is a non-empty prefix which is also a suffix of the string, excluding the entire string itself.

Given a string s, return the longest happy prefix of s. If no such prefix exists, return an empty string "".

In other words, you need to find the longest substring that appears at both the very beginning and the very end of the string — but the substring cannot be the entire string.

Note that the prefix and suffix are allowed to overlap within the original string. For instance, in "ababab", the prefix "abab" (positions 0–3) and the suffix "abab" (positions 2–5) overlap in the middle, and that is valid.

Examples

Example 1

Input: s = "level"

Output: "l"

Explanation: The string "level" has the following proper prefixes: "l", "le", "lev", "leve". It has the following proper suffixes: "l", "el", "vel", "evel". The only prefix that is also a suffix is "l". So the longest happy prefix is "l".

Example 2

Input: s = "ababab"

Output: "abab"

Explanation: The proper prefixes of "ababab" are: "a", "ab", "aba", "abab", "ababa". The proper suffixes are: "b", "ab", "bab", "abab", "babab". Prefixes that are also suffixes: "ab" (length 2) and "abab" (length 4). The longest one is "abab".

Example 3

Input: s = "a"

Output: ""

Explanation: The string "a" has no proper prefix (a proper prefix cannot be the entire string). So there is no happy prefix and we return an empty string.

Constraints

  • 1 ≤ s.length ≤ 10^5
  • s contains only lowercase English letters.

Editorial

Brute Force

Intuition

The most natural approach is to simply try every possible length and check whether the prefix of that length matches the suffix of the same length.

Imagine you have a long ribbon with letters printed on it. You want to fold one end of the ribbon over and see if it matches the other end. You start with the longest possible fold (just short of the entire ribbon) and keep shortening until you find a match — or run out of options.

Concretely, for a string of length n, we try lengths from n-1 down to 1. For each candidate length len, we extract the first len characters (the prefix) and the last len characters (the suffix), then compare them character by character. The first length where they match is our answer.

Step-by-Step Explanation

Let's trace through with s = "level":

Step 1: Try length 4 (longest possible proper prefix/suffix).

  • Prefix: s[0..3] = "leve"
  • Suffix: s[1..4] = "evel"
  • Compare: 'l' vs 'e' → mismatch at first character. Not equal.

Step 2: Try length 3.

  • Prefix: s[0..2] = "lev"
  • Suffix: s[2..4] = "vel"
  • Compare: 'l' vs 'v' → mismatch at first character. Not equal.

Step 3: Try length 2.

  • Prefix: s[0..1] = "le"
  • Suffix: s[3..4] = "el"
  • Compare: 'l' vs 'e' → mismatch at first character. Not equal.

Step 4: Try length 1.

  • Prefix: s[0] = "l"
  • Suffix: s[4] = "l"
  • Compare: 'l' vs 'l' → match! Found a happy prefix.

Step 5: Return "l".

Result: "l"

Brute Force — Trying Each Prefix Length Against Suffix — Watch how we try progressively shorter candidate lengths until we find a prefix that matches the corresponding suffix.

Algorithm

  1. For each candidate length len from n-1 down to 1:
    • Extract the prefix: s[0..len-1].
    • Extract the suffix: s[n-len..n-1].
    • Compare the prefix and suffix character by character.
    • If they are equal, return this prefix as the longest happy prefix.
  2. If no match is found for any length, return an empty string "".

Code

class Solution {
public:
    string longestPrefix(string s) {
        int n = s.size();
        
        // Try each possible length from longest to shortest
        for (int len = n - 1; len >= 1; len--) {
            bool match = true;
            for (int k = 0; k < len; k++) {
                if (s[k] != s[n - len + k]) {
                    match = false;
                    break;
                }
            }
            if (match) {
                return s.substr(0, len);
            }
        }
        
        return "";
    }
};
class Solution:
    def longestPrefix(self, s: str) -> str:
        n = len(s)
        
        # Try each possible length from longest to shortest
        for length in range(n - 1, 0, -1):
            if s[:length] == s[n - length:]:
                return s[:length]
        
        return ""
class Solution {
    public String longestPrefix(String s) {
        int n = s.length();
        
        // Try each possible length from longest to shortest
        for (int len = n - 1; len >= 1; len--) {
            boolean match = true;
            for (int k = 0; k < len; k++) {
                if (s.charAt(k) != s.charAt(n - len + k)) {
                    match = false;
                    break;
                }
            }
            if (match) {
                return s.substring(0, len);
            }
        }
        
        return "";
    }
}

Complexity Analysis

Time Complexity: O(n²)

We try up to n-1 candidate lengths. For each candidate of length len, we compare len characters. In the worst case (e.g., s = "abcde..."), no long prefix matches, and we compare approximately n + (n-1) + (n-2) + … + 1 = n(n-1)/2 characters. This is O(n²).

Space Complexity: O(n)

The substring extraction for comparison and the result string use O(n) space. The comparison logic itself uses O(1) extra space beyond the substrings.

Why This Approach Is Not Efficient

The brute force approach compares prefixes and suffixes character-by-character for every candidate length. With n up to 10⁵, the O(n²) time means up to 10¹⁰ operations in the worst case — far beyond what can execute within time limits.

The fundamental problem is that we start fresh for each candidate length. When we check if the prefix of length 5 matches the suffix of length 5, and it fails at character position 3, we throw away everything we learned. The next check (length 4) starts from scratch instead of leveraging the partial matching information.

The KMP algorithm's LPS (Longest Proper Prefix which is also Suffix) array solves this elegantly. Instead of checking each length independently, it builds a table in O(n) time where the last entry directly gives us the length of the longest happy prefix — using the same "fallback" mechanism that makes KMP pattern matching so efficient.

Optimal Approach - KMP (LPS Array)

Intuition

The problem of finding the longest happy prefix is exactly what the KMP preprocessing step (the LPS array) was designed to solve.

The LPS array for a string s of length n is defined as follows: lps[i] stores the length of the longest proper prefix of the substring s[0..i] that is also a suffix of s[0..i]. "Proper" means it cannot be the entire substring itself.

So lps[n-1] — the last entry of the LPS array — gives us exactly what we want: the length of the longest proper prefix of the entire string that is also a suffix.

The genius of the LPS construction is its fallback mechanism. When we try to extend a match and encounter a mismatch, instead of starting over, we "fall back" to a shorter prefix that we already know matches. This is possible because if s[0..k-1] matches s[i-k..i-1], then we can check if there's a shorter prefix of s[0..k-1] that also matches — and that answer is stored in lps[k-1].

Think of it like a zipper. As we scan the string from left to right, we try to "zip up" the beginning of the string with the current position. When we encounter a mismatch, instead of unzipping all the way, we jump back to the last known good position where partial alignment still holds — and try from there.

Diagram showing the LPS array for 'ababab' with prefix-suffix matches highlighted
Diagram showing the LPS array for 'ababab' with prefix-suffix matches highlighted

Step-by-Step Explanation

Let's trace the LPS array construction for s = "ababab":

Step 1: Initialize lps[0] = 0 (single character has no proper prefix). Set len = 0, i = 1.

Step 2: i=1, s[1]='b'. Compare s[1] with s[0]='a'. Mismatch. len is already 0, so lps[1]=0. Move i to 2.

Step 3: i=2, s[2]='a'. Compare s[2] with s[0]='a'. Match! Increment len to 1, set lps[2]=1. Move i to 3.

  • This means: in substring "aba", the prefix "a" matches the suffix "a".

Step 4: i=3, s[3]='b'. Compare s[3] with s[1]='b'. Match! Increment len to 2, set lps[3]=2. Move i to 4.

  • This means: in substring "abab", the prefix "ab" matches the suffix "ab".

Step 5: i=4, s[4]='a'. Compare s[4] with s[2]='a'. Match! Increment len to 3, set lps[4]=3. Move i to 5.

  • This means: in substring "ababa", the prefix "aba" matches the suffix "aba".

Step 6: i=5, s[5]='b'. Compare s[5] with s[3]='b'. Match! Increment len to 4, set lps[5]=4. Move i to 6.

  • This means: in substring "ababab", the prefix "abab" matches the suffix "abab".

Step 7: i=6, which equals n=6. LPS construction complete.

Step 8: lps[n-1] = lps[5] = 4. The longest happy prefix has length 4, which is s[0..3] = "abab".

Result: "abab"

KMP LPS Array Construction for "ababab" — Watch how the LPS array is built by comparing each new character with the character at the current match length, using the fallback mechanism on mismatches.

Algorithm

  1. Initialize an LPS array of size n with all zeros.
  2. Set len = 0 (length of the previous longest prefix-suffix), i = 1.
  3. While i < n:
    • If s[i] == s[len]: increment len, set lps[i] = len, increment i.
    • Else if len > 0: fall back by setting len = lps[len - 1] (don't increment i — retry the comparison with the shorter prefix).
    • Else: lps[i] = 0, increment i.
  4. The answer length is lps[n - 1].
  5. Return s[0..lps[n-1]-1] (the prefix of that length).

Code

class Solution {
public:
    string longestPrefix(string s) {
        int n = s.size();
        vector<int> lps(n, 0);
        
        int len = 0;  // length of previous longest prefix-suffix
        int i = 1;
        
        while (i < n) {
            if (s[i] == s[len]) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    // Fall back to the previous best match
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        
        // lps[n-1] is the length of longest happy prefix
        return s.substr(0, lps[n - 1]);
    }
};
class Solution:
    def longestPrefix(self, s: str) -> str:
        n = len(s)
        lps = [0] * n
        
        length = 0  # length of previous longest prefix-suffix
        i = 1
        
        while i < n:
            if s[i] == s[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    # Fall back to the previous best match
                    length = lps[length - 1]
                else:
                    lps[i] = 0
                    i += 1
        
        # lps[n-1] is the length of longest happy prefix
        return s[:lps[n - 1]]
class Solution {
    public String longestPrefix(String s) {
        int n = s.length();
        int[] lps = new int[n];
        
        int len = 0;  // length of previous longest prefix-suffix
        int i = 1;
        
        while (i < n) {
            if (s.charAt(i) == s.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    // Fall back to the previous best match
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        
        // lps[n-1] is the length of longest happy prefix
        return s.substring(0, lps[n - 1]);
    }
}

Complexity Analysis

Time Complexity: O(n)

The LPS array is built in a single pass. Although there is a while loop with an inner fallback operation (len = lps[len - 1]), the total number of operations is bounded by O(n). The key insight is that len can increase at most n times total (once per character match), and each fallback decreases len by at least 1. Since len starts at 0 and never goes below 0, the total number of fallbacks across all iterations cannot exceed n. Therefore, the combined work of advancing i and performing fallbacks is O(n).

Space Complexity: O(n)

The LPS array requires O(n) space. The output string is at most O(n) in length. All other variables use O(1) space.