Longest Happy Prefix - Practice Coding Problems

Longest Happy Prefix - Problem

A string is called a happy prefix if it 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.

Note: A prefix must be different from the string itself - we cannot use the entire string as both prefix and suffix.

Input & Output

Example 1 — Basic Case

$ Input: s = "level"

› Output: "l"

💡 Note: The longest happy prefix is "l" because it appears at both the beginning and end of "level". Other prefixes like "le", "lev", "leve" don't match their corresponding suffixes.

Example 2 — No Happy Prefix

$ Input: s = "ababab"

› Output: "abab"

💡 Note: The prefix "abab" also appears as suffix "abab" in "ababab". This is the longest such match.

Example 3 — No Match

$ Input: s = "leetcodeleet"

› Output: "leet"

💡 Note: The prefix "leet" matches the suffix "leet" in "leetcodeleet". No longer prefix has this property.

Constraints

1 ≤ s.length ≤ 10⁵
s consists of lowercase English letters.

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Given string with potential prefix-suffix matches

Pattern Recognition

Find longest prefix that equals some suffix

Output Result

Return the matching prefix string

Key Takeaway

🎯 Key Insight: Use KMP failure function to find longest proper prefix that's also suffix in O(n) time

Asked in

F Facebook 15 G Google 12 a Amazon 8

The key insight is that this problem is equivalent to finding the longest proper prefix which is also a suffix - exactly what the KMP failure function computes. The optimal KMP approach runs in O(n) time and directly gives us the answer at failure[n-1]. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ KMP Failure Function	O(n)	O(n)	Use KMP preprocessing to find longest proper prefix-suffix match
Hash Map Optimization	O(n²)	O(n²)	Store all prefixes in hash map, then check suffixes
Brute Force	O(n²)	O(1)	Check every prefix against every suffix

KMP Failure Function — Algorithm Steps

Step 1: Build KMP failure function array
Step 2: Track longest proper prefix-suffix at each position
Step 3: Return prefix of length failure[n-1]

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with failure array [0,0,0,0,0] and j=0

Process Each Position

For each character, find longest proper prefix that's also suffix

Final Result

failure[n-1] gives length of longest happy prefix

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(char* s) {
    int n = strlen(s);
    char* result = (char*)malloc((n + 1) * sizeof(char));
    
    if (n <= 1) {
        result[0] = '\0';
        return result;
    }
    
    // Build KMP failure function
    int* failure = (int*)calloc(n, sizeof(int));
    int j = 0;
    
    for (int i = 1; i < n; i++) {
        while (j > 0 && s[i] != s[j]) {
            j = failure[j - 1];
        }
        
        if (s[i] == s[j]) {
            j++;
        }
        
        failure[i] = j;
    }
    
    // The failure value at last position gives longest happy prefix length
    int happyLength = failure[n - 1];
    strncpy(result, s, happyLength);
    result[happyLength] = '\0';
    
    free(failure);
    return result;
}

int main() {
    char s[100001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char* result = solution(s);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through string to build failure function, each character processed once

✓ Linear Growth

Space Complexity

O(n)

Failure function array of size n

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

987 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

KMP Failure Function — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler