Shortest Palindrome Solution in Java

Explore Solutions in Other Languages

Problem Description

Ah, the Shortest Palindrome problem! It’s like trying to find the quickest route to your favorite coffee shop, only to realize you have to detour through a maze of one-way streets. The task is simple: given a string s, you need to find the shortest palindrome that can be formed by adding characters in front of it.

Imagine you’re at a party, and you want to impress everyone with your dance moves. But alas, you realize you can only do the Macarena. So, you decide to add some fancy footwork in front of it to make it look like a masterpiece. That’s exactly what we’re doing here—adding characters to the front of a string to make it a palindrome!

Code Solution


class Solution {
  public String shortestPalindrome(String s) {
    final String t = new StringBuilder(s).reverse().toString();

    for (int i = 0; i < t.length(); ++i)
      if (s.startsWith(t.substring(i)))
        return t.substring(0, i) + s;

    return t + s;
  }
}

Approach Explanation

The approach here is as straightforward as it gets. We first reverse the string s to create t. Then, we check how much of the reversed string t matches the start of the original string s. The moment we find a match, we know how many characters we need to add to the front of s to make it a palindrome. If no match is found, we simply prepend the entire reversed string t to s. Voilà!

Time and Space Complexity

Time Complexity: O(n²) in the worst case, where n is the length of the string. This is due to the substring operations inside the loop.

Space Complexity: O(n) for storing the reversed string.

Real-World Example

Let’s say you’re trying to create a catchy username for your new social media account. You start with "user123". But, oh no! You realize that "321resu" is the coolest way to present it. So, you add "321" in front of "user123" to make it "321user123". Now, you’re not just a user; you’re a trendsetter!