The O(n) Club: Turning Your String Into a Narcissist—Shortest Palindrome Edition

The O(n) Club: Turning Your String Into a Narcissist—Shortest Palindrome Edition

⚡ TL;DR

You want to turn your string s into the shortest palindrome by only adding letters to its front. Brute force means searching every possible prefix for an existing palindrome—you’ll get the answer, but also carpal tunnel.

// Brute force O(n^2); works, just don't blink during the interview
String shortestPalindrome(String s) {
    for (int i = s.length(); i >= 0; i--) {
        if (isPalindrome(s, 0, i - 1)) {
            StringBuilder sb = new StringBuilder(s.substring(i));
            return sb.reverse().toString() + s;
        }
    }
    return "";
}
boolean isPalindrome(String s, int l, int r) {
    while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
    return true;
}

🧠 How Devs Usually Mess This Up

It’s always the same greatest hits: searching for any palindrome anywhere, tacking stuff onto the end (nope!), or just praying a solution falls out if you reverse something “because it worked on LeetCode once.” Sorry—only palindromic prefixes matter, and you can only slap chars on at the front. Everyone else is just wasting caffeine.

🔍 What’s Actually Going On

Think of your string as a party line: the prefix is the sober chaperone, the suffix is doing the worm on the dance floor. The shortest palindrome trick? Find the longest chaperone (palindromic prefix)—then reverse whatever chaos is left in the suffix and stick it up front. Suddenly everyone’s classy, and you only did minimal work. Your string, newly dignified and symmetrical, is ready for algorithmic tea.

🛠️ PseudoCode

• Reverse the input string.

  String rev = new StringBuilder(s).reverse().toString();

  Creates a bizarro version of your party—the mirror world.
• Find the largest i where s starts with rev.substring(i).

  for (int i = 0; i <= s.length(); i++) {
      if (s.startsWith(rev.substring(i))) {
          // Found the palindromic prefix's mirror overlap!
      }
  }

  The first overlap from the end means fewer letters glued on.
• Prepend the non-palindromic suffix (reversed).

  String add = rev.substring(0, i);
  return add + s;
  

  Voilà! The shortest possible full-palindrome, no shortcuts.

💻 The Code

// O(n^2) solution
public String shortestPalindrome(String s) {
    String rev = new StringBuilder(s).reverse().toString();
    int n = s.length();
    for (int i = 0; i <= n; i++) {
        if (s.startsWith(rev.substring(i))) {
            return rev.substring(0, i) + s;
        }
    }
    return s; // In case someone gives empty string—bold choice
}
 // O(n) version, for devs craving performance and migraines
public String shortestPalindromeKMP(String s) {
    String rev = new StringBuilder(s).reverse().toString();
    String temp = s + "#" + rev;
    int[] lps = new int[temp.length()];
    for (int i = 1; i < temp.length(); i++) {
        int len = lps[i - 1];
        while (len > 0 && temp.charAt(i) != temp.charAt(len)) {
            len = lps[len - 1];
        }
        if (temp.charAt(i) == temp.charAt(len)) len++;
        lps[i] = len;
    }
    String add = rev.substring(0, s.length() - lps[temp.length() - 1]);
    return add + s;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Palindromes in the middle? Worthless here. Only prefixes get loyalty points.
• Single letters and blank strings sneak by—don’t overthink your edge cases.
• Messing with substring indices? Prepare for Off-by-One Land.
• O(n^2) fine for hacks, but only O(n) solutions win bonus interview karma.

🧠 Interviewer Brain-Tattoo

“When in doubt, trust your prefix. Append to the front and stop hoping palindromes in the middle will save your runtime. Your string wants to be admired from the start.”