Coding

Shortest Palindrome

Asked at

Oracle

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given a string s convert it into a palindrome by adding characters to the beginning of it. Return the shortest palindrome you can create by performing this transformation.

Input: s = "aacecaaa" Output: aaacecaaa Explanation: Adding "a" to the front of "aacecaaa" makes it a palindrome: "aaacecaaa".

Input: s = "race" Output: ecarace Explanation: By adding "eca" in front of "race", the shortest palindrome "ecarace" is formed.

Input: s = "abcd"

1 <= s.length <= 104

cpp

class Solution{
  public:		
	string shortestPalindrome(string s) {
	     
	}
};

java

class Solution {
    public String shortestPalindrome(String s) {
  
    }
}

python

class Solution:
    def shortestPalindrome(self, s: str) -> str:

javascript

class Solution {
    shortestPalindrome(s) {
      
    }
}

csharp

class Solution {
    public string ShortestPalindrome(string s) {

    }
}

func shortestPalindrome(s string) string {

}

Stuck? Show a way to structure it+

01Reverse the input.
02Concatenate original, a delimiter, and reversed.
03Compute its prefix function.
04Use the final value as longest palindromic prefix length.
05Prepend the unmatched reversed suffix.

Reference answer

Only the longest prefix of s that is already a palindrome can remain fixed; every character after it must be mirrored in front. Let rev be reverse(s), and compute the KMP prefix function for s plus a delimiter not in the alphabet plus rev. The final prefix value L is the longest prefix of s matching a suffix of rev, which is exactly the longest palindromic prefix of s. The answer is rev.substring(0, n minus L) concatenated with s. For "race", L is 1, so prepend "eca" and obtain "ecarace". A delimiter is essential to prevent matches crossing from s into rev incorrectly. KMP construction is O(n) time and O(n) space. Checking progressively shorter prefixes for palindromicity is O(n squared) in the worst case.

Then expect these follow-ups

Can a rolling hash implement this with collision risk?
Tests: implementation extension
How would you build the shortest palindrome by appending instead?
Tests: follow-up reasoning

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question