Shortest Palindrome - Practice Coding Problems

Shortest Palindrome - Problem

You are given a string s. You can convert s to a palindrome by adding characters in front of it. Return the shortest palindrome you can find by performing this transformation.

A palindrome is a string that reads the same forward and backward.

Input & Output

Example 1 — Basic Case

$ Input: s = "aacecaaa"

› Output: "aaacecaaa"

💡 Note: The optimal palindrome is "aaacecaaa" by adding "aa" to the front. The longest palindromic prefix is "aaceca", so we add the remaining "aa" (reversed) to the front.

Example 2 — Already Palindrome

$ Input: s = "abcd"

› Output: "dcbabcd"

💡 Note: Since "abcd" has no palindromic prefix except empty string, we need to add "dcb" (reverse of "bcd") to make it "dcbabcd".

Example 3 — Single Character

$ Input: s = "a"

› Output: "a"

💡 Note: A single character is already a palindrome, so no characters need to be added.

Constraints

0 ≤ s.length ≤ 5 × 10⁴
s consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input String

Original string that needs to become palindrome

Find Prefix

Identify the longest palindromic prefix

Add Characters

Add minimum characters to front to form palindrome

Key Takeaway

🎯 Key Insight: Find the longest palindromic prefix, then add only the non-overlapping suffix (reversed) to minimize additions

Asked in

G Google 45 f Facebook 38 a Amazon 32 M Microsoft 28

The key insight is to find the longest palindromic prefix and add only the necessary suffix characters (reversed) to the front. The optimal approach uses KMP algorithm with pattern s + '#' + reverse(s) to find the overlap in O(n) time. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers Optimization	O(n²)	O(n)	Find the longest palindromic prefix to minimize characters added
Brute Force Check	O(n³)	O(n)	Try adding characters one by one until we get a palindrome
KMP Algorithm (Rolling Hash)	O(n)	O(n)	Use KMP failure function to find the longest prefix-suffix match efficiently

Two Pointers Optimization — Algorithm Steps

Step 1: Use two pointers from start and end
Step 2: Find longest palindromic prefix
Step 3: Add remaining suffix (reversed) to front
Step 4: Return the constructed palindrome

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Full String

Use pointers to check if entire string is palindrome

Shrink Right

If not palindrome, move right pointer left

Found Prefix

When palindrome found, add remaining suffix reversed

Code -

solution.c — C

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

int isPalindromeFrom(const char* s, int start, int end) {
    while (start < end) {
        if (s[start] != s[end]) {
            return 0;
        }
        start++;
        end--;
    }
    return 1;
}

void reverse_substring(char* dest, const char* src, int start, int len) {
    for (int i = 0; i < len; i++) {
        dest[i] = src[start + len - 1 - i];
    }
    dest[len] = '\0';
}

char* solution(char* s) {
    int n = strlen(s);
    char* result = (char*)malloc(2 * n + 1);
    
    // Find the longest palindromic prefix
    for (int i = 0; i < n; i++) {
        if (isPalindromeFrom(s, 0, n - 1 - i)) {
            // Found palindromic prefix, add suffix reversed to front
            char suffix[1001];
            reverse_substring(suffix, s, n - i, i);
            strcpy(result, suffix);
            strcat(result, s);
            return result;
        }
    }
    
    strcpy(result, s);
    return result;
}

int main() {
    char s[1001];
    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²)

Outer loop tries n starting positions, inner palindrome check takes O(n) time

⚠ Quadratic Growth

Space Complexity

O(n)

Creating the result string and temporary substrings

⚡ Linearithmic Space

89.4K Views

Medium Frequency

~25 min Avg. Time

1.8K 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

Two Pointers Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler