Shortest Palindrome

HARD

Description

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.

Example 1:

Input: s = "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: s = "abcd"
Output: "dcbabcd"

Constraints:

0 <= s.length <= 5 * 10⁴
s consists of lowercase English letters only.

Approaches

Checkout 2 different approaches to solve Shortest Palindrome. Click on different approaches to view the approach and algorithm in detail.

Brute Force Approach

Check each prefix of the string to find the longest palindrome starting from index 0, then add the remaining characters in reverse order to the front.

Algorithm

Iterate through each prefix of the string from index 0 to n-1
For each prefix, check if it forms a palindrome
Keep track of the longest palindrome prefix
Take the remaining characters after the longest palindrome prefix
Reverse these characters and add them to the front of the original string

In this approach, we iterate through each prefix of the string and check if it forms a palindrome starting from index 0. Once we find the longest palindrome prefix, we take the remaining characters, reverse them, and add them to the front of the original string.

public String shortestPalindrome(String s) {
    int n = s.length();
    int maxLen = 0;
    
    // Check each prefix
    for (int i = 0; i < n; i++) {
        if (isPalindrome(s, 0, i)) {
            maxLen = i + 1;
        }
    }
    
    // Get the remaining characters and reverse them
    String remaining = s.substring(maxLen);
    StringBuilder reversed = new StringBuilder(remaining).reverse();
    
    return reversed.toString() + s;
}

private boolean isPalindrome(String s, int start, int end) {
    while (start < end) {
        if (s.charAt(start) != s.charAt(end)) {
            return false;
        }
        start++;
        end--;
    }
    return true;
}

Complexity Analysis

Time Complexity: O(n²) where n is the length of the string - we need to check each prefix and for each prefix we check if it's a palindromeSpace Complexity: O(n) for storing the reversed substring

Pros and Cons

Pros:

Simple to understand and implement
Works well for small strings

Cons:

Very inefficient for large strings
Performs redundant checks for palindrome verification

Code Solutions

Checking out 4 solutions in different languages for Shortest Palindrome. Click on different languages to view the code.

// https://leetcode.com/problems/shortest-palindrome/ using System.Text ; public partial class Solution { public string ShortestPalindrome ( string s ) { for ( var i = s . Length - 1 ; i >= 0 ; -- i ) { var k = i ; var j = 0 ; while ( j < k ) { if ( s [ j ] == s [ k ]) { ++ j ; -- k ; } else { break ; } } if ( j >= k ) { var sb = new StringBuilder ( s . Length * 2 - i - 1 ); for ( var l = s . Length - 1 ; l >= i + 1 ; -- l ) { sb . Append ( s [ l ]); } sb . Append ( s ); return sb . ToString (); } } return string . Empty ; } }

Video Solution

Watch the video walkthrough for Shortest Palindrome

Patterns:

String MatchingRolling HashHash Function

Data Structures:

String

Companies:

Accenture |Google |Visa |eBay |