LeetCode – Q214 – Shortest Palindrome

This question, despite being solvable by a simple O(n^2) algorithm, almost took 2 hours of my life.

Simply because I was trying to get sub-palindromes, when instead, I should have checked for longest prefix of original string matching the suffix of its reverse.

E.g.           s = “abcda”

              reverse of s = rev = “adcba”

         longest suffix of rev matching s = “a”

              Answer = “adcbabcda”

class Solution {
    string shortestPalindrome(string s) {
        string rev = s;
        int n = s.size();
        for(int i=n;i>0;i–)
                return rev.substr(0,n-i)+s;
        return rev+s;


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s