How do you solve Shortest Palindrome on LeetCode?

Shortest Palindrome (LeetCode #214) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using KMP helps avoid redundant checks for palindromes.

What is the brute force solution for Shortest Palindrome?

The brute force approach for Shortest Palindrome is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves checking all possible prefixes of the string and determining the shortest palindrome we can form by adding characters in front. This method is straightforward but inefficient for larger strings. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Shortest Palindrome?

Shortest Palindrome uses the following concepts: String, Rolling Hash, String Matching, Hash Function. The recommended patterns to study are: String Matching, KMP Algorithm.

What are the interview tips for Shortest Palindrome?

Explain your thought process clearly while coding. Discuss the trade-offs of different approaches. Practice building KMP tables as they are common in string problems.

What are common mistakes when solving Shortest Palindrome?

Not checking for empty strings. Overlooking the need for a separator when combining strings.

#214

Shortest Palindrome

Hard

StringRolling HashString MatchingHash FunctionString MatchingKMP Algorithm

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses the concept of the KMP (Knuth-Morris-Pratt) algorithm to find the longest palindromic prefix efficiently. By constructing a new string that combines the original string and its reverse, we can leverage the KMP table to find the longest matching prefix.

⚙️

Algorithm

3 steps

1Step 1: Create a new string that combines the original string, a separator (like '#'), and the reverse of the original string.
2Step 2: Build the KMP table for this new string to find the length of the longest palindromic prefix.
3Step 3: Use this length to determine how many characters need to be added in front of the original string to form the shortest palindrome.

solution.py13 lines

1def shortest_palindrome(s):
2    if not s: return s
3    rev = s[::-1]
4    new_s = s + '#' + rev
5    lps = [0] * len(new_s)
6    j = 0
7    for i in range(1, len(new_s)):
8        while j > 0 and new_s[i] != new_s[j]:
9            j = lps[j - 1]
10        if new_s[i] == new_s[j]:
11            j += 1
12            lps[i] = j
13    return rev[:len(s) - lps[-1]] + s

ℹ

Complexity note: The time complexity is O(n) due to the linear scan for building the KMP table, and the space complexity is O(n) for storing the KMP table and the new string.

1Using KMP helps avoid redundant checks for palindromes.
2Combining the string with its reverse allows us to leverage string matching techniques.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.