LeetCode 1312 - Minimum Insertion Steps to Make a String Palindrome

Edit The problem gives us a string s and asks for the minimum number of insertion operations required to transform the s

leetcodehardstringdynamic-programming

LeetCode Problem 1312

Difficulty: 🔴 Hard
Topics: String, Dynamic Programming

Solution

Edit

LeetCode 1312 - Minimum Insertion Steps to Make a String Palindrome

Problem Understanding

The problem gives us a string s and asks for the minimum number of insertion operations required to transform the string into a palindrome. In a single operation, we may insert any lowercase English character at any position in the string. The inserted character does not have to match an existing character, and we are free to insert at the beginning, middle, or end.

A palindrome is a string that reads the same from left to right and right to left. Examples include "racecar", "abba", and "zzazz". The goal is not to return the resulting palindrome itself, but only the minimum number of insertions required to make the given string palindromic.

To understand the task more clearly, consider the string "mbadm". This string is not currently a palindrome because characters do not mirror each other symmetrically. However, by inserting two characters, we can transform it into "mbdadbm" or "mdbabdm". Since this can be done in two insertions and no solution requires fewer operations, the answer is 2.

The input consists of a single string s, where:

  • 1 <= s.length <= 500
  • s contains only lowercase English letters

The maximum string length of 500 is important because it strongly suggests that a quadratic time dynamic programming solution, O(n²), is feasible, while exponential approaches would be too slow.

There are several edge cases worth considering early:

  • A string that is already a palindrome, such as "zzazz", should return 0.
  • A single-character string is always a palindrome and therefore requires 0 insertions.
  • Strings with all unique characters, such as "abc", may require several insertions.
  • Strings with repeated characters but poor symmetry, such as "leetcode", can still require many insertions.
  • Very long strings near the limit of 500 characters require an efficient algorithm because brute force would be computationally infeasible.

The problem guarantees valid lowercase input and a non-empty string, so we do not need to handle invalid or null inputs.

Approaches

Brute Force Approach

A naive way to solve this problem would be to recursively try inserting every possible character at every possible position and check whether the resulting string becomes a palindrome. For every mismatch between characters, we could branch into multiple recursive possibilities and attempt all insertion combinations.

For example, if characters at the left and right ends do not match, we could try:

  1. Inserting the left character near the right side.
  2. Inserting the right character near the left side.
  3. Exploring both possibilities recursively.

Eventually, we would generate every possible valid transformation and choose the one requiring the fewest insertions.

This approach is correct because it explores the entire search space of insertion possibilities. However, it is far too slow. The number of possible insertion combinations grows exponentially, making it impractical for strings up to length 500.

A memoized recursive approach could reduce repeated work, but a better insight allows us to formulate a clean dynamic programming solution.

Key Insight

Instead of thinking about what to insert, it is easier to think about what we can preserve.

A palindrome is symmetric. Therefore, if we can identify the longest subsequence that is already palindromic, we only need to insert characters around the remaining parts.

This observation transforms the problem into:

Minimum insertions = Length of string - Length of longest palindromic subsequence (LPS)

Why does this work?

Suppose the string has length n and the longest palindromic subsequence has length L.

The subsequence already forms the symmetric core of the palindrome. Every remaining character outside that subsequence must be matched by inserting corresponding characters. Therefore, we need exactly n - L insertions.

Now the question becomes:

How do we efficiently compute the longest palindromic subsequence?

A useful trick is that:

The longest palindromic subsequence of s equals the longest common subsequence (LCS) between s and reverse(s).

We can therefore solve this using classic dynamic programming for LCS.

Approach Time Complexity Space Complexity Notes
Brute Force O(2ⁿ) or worse O(n) recursion Tries many insertion combinations recursively
Optimal Dynamic Programming O(n²) O(n²) Computes longest palindromic subsequence using LCS

Algorithm Walkthrough

We will compute the Longest Common Subsequence (LCS) between the original string and its reversed version.

Step 1: Reverse the string

Create a reversed copy of the string.

If:

s = "mbadm"

Then:

reversed_s = "mdabm"

Any palindromic subsequence appears in the same order in both strings.

Step 2: Create a DP table

We create a dp table where:

dp[i][j]

represents the length of the Longest Common Subsequence between:

s[:i]

and:

reversed_s[:j]

The table dimensions are:

(n + 1) x (n + 1)

We use an extra row and column initialized to 0 to simplify boundary conditions.

Step 3: Fill the table

Iterate through both strings.

If characters match:

s[i - 1] == reversed_s[j - 1]

we extend the subsequence:

dp[i][j] = dp[i - 1][j - 1] + 1

If characters do not match:

dp[i][j] = max(
    dp[i - 1][j],
    dp[i][j - 1]
)

This ensures we keep the best subsequence length discovered so far.

Step 4: Get the longest palindromic subsequence

After filling the table:

dp[n][n]

contains the length of the longest palindromic subsequence.

Step 5: Compute minimum insertions

Finally:

answer = n - longest_palindromic_subsequence

This gives the minimum number of insertions needed.

Why it works

The key invariant is that dp[i][j] always stores the length of the best common subsequence between prefixes of the original string and reversed string.

Since a palindrome reads identically forward and backward, any palindromic subsequence appears in both the string and its reverse. Therefore, the LCS of the string and its reverse is exactly the longest palindromic subsequence.

Once we know the largest symmetric portion already present, every remaining unmatched character must be mirrored through insertion. Thus:

minimum insertions = n - LPS

guaranteeing correctness.

Python Solution

class Solution:
    def minInsertions(self, s: str) -> int:
        n = len(s)
        reversed_s = s[::-1]

        dp = [[0] * (n + 1) for _ in range(n + 1)]

        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if s[i - 1] == reversed_s[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(
                        dp[i - 1][j],
                        dp[i][j - 1]
                    )

        longest_palindromic_subsequence = dp[n][n]

        return n - longest_palindromic_subsequence

The implementation begins by computing the reversed version of the string. Since we want the longest palindromic subsequence, we convert the problem into an LCS computation between the original string and its reverse.

We then create a dynamic programming table where each cell stores the LCS length for two prefixes. The extra row and column initialized to zero make boundary handling easier because empty prefixes naturally have subsequence length 0.

The nested loops compare characters one by one. When characters match, we extend a valid subsequence from the diagonal cell. When they differ, we inherit the best result from either removing a character from the original string or from the reversed string.

After the table is complete, dp[n][n] stores the longest palindromic subsequence length. Subtracting this value from the original length gives the minimum insertions needed.

Go Solution

func minInsertions(s string) int {
	n := len(s)

	reversed := reverseString(s)

	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}

	for i := 1; i <= n; i++ {
		for j := 1; j <= n; j++ {
			if s[i-1] == reversed[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				dp[i][j] = max(
					dp[i-1][j],
					dp[i][j-1],
				)
			}
		}
	}

	longestPalindromicSubsequence := dp[n][n]

	return n - longestPalindromicSubsequence
}

func reverseString(s string) string {
	bytes := []byte(s)

	left := 0
	right := len(bytes) - 1

	for left < right {
		bytes[left], bytes[right] =
			bytes[right], bytes[left]

		left++
		right--
	}

	return string(bytes)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

The Go implementation follows the same dynamic programming structure as the Python version. Since Go does not provide built-in string reversal, we implement a helper function that reverses the byte slice in place.

Unlike Python lists, Go requires explicit allocation of a two-dimensional slice using make. We initialize every row individually.

Integer overflow is not a concern because the maximum DP value is at most 500, which easily fits inside Go's int type.

Since the input is guaranteed to be non-empty and contains lowercase English letters, we do not need additional input validation.

Worked Examples

Example 1

s = "zzazz"

The string is already a palindrome.

Reverse:

"zzazz"

The LCS between the string and itself is 5.

Value Result
String Length 5
Longest Palindromic Subsequence 5
Minimum Insertions 0

Result:

5 - 5 = 0

Example 2

s = "mbadm"

Reverse:

"mdabm"

Key DP progression:

i j s[i-1] reversed[j-1] Match? dp[i][j]
1 1 m m Yes 1
2 2 b d No 1
3 3 a a Yes 2
4 4 d b No 2
5 5 m m Yes 3

Longest palindromic subsequence:

"mam" or "mdm"

Length:

3

Final computation:

Value Result
String Length 5
LPS Length 3
Minimum Insertions 2

Answer:

5 - 3 = 2

Example 3

s = "leetcode"

Reverse:

"edocteel"

The DP table eventually finds:

Longest Palindromic Subsequence = 3

One valid subsequence is:

"ete"

Final calculation:

Value Result
String Length 8
LPS Length 3
Minimum Insertions 5

Answer:

8 - 3 = 5

Complexity Analysis

Measure Complexity Explanation
Time O(n²) We fill an n × n DP table
Space O(n²) The DP table stores n² values

The dynamic programming table has (n + 1) × (n + 1) cells. Each cell is computed in constant time using previously computed states, resulting in quadratic time complexity.

Since n ≤ 500, the algorithm performs at most about 250,000 DP updates, which is efficient for the problem constraints.

Test Cases

solution = Solution()

assert solution.minInsertions("zzazz") == 0  # already palindrome
assert solution.minInsertions("mbadm") == 2  # example case
assert solution.minInsertions("leetcode") == 5  # example case

assert solution.minInsertions("a") == 0  # single character
assert solution.minInsertions("aa") == 0  # already palindrome
assert solution.minInsertions("ab") == 1  # one insertion needed

assert solution.minInsertions("abc") == 2  # all unique chars
assert solution.minInsertions("abcd") == 3  # increasing mismatch

assert solution.minInsertions("race") == 3  # partial symmetry
assert solution.minInsertions("abcba") == 0  # odd palindrome
assert solution.minInsertions("abccba") == 0  # even palindrome

assert solution.minInsertions("banana") == 1  # repeated chars
assert solution.minInsertions("google") == 2  # repeated letters

assert solution.minInsertions("abcdefghijklmnopqrstuvwxyz") == 25  # max mismatch
assert solution.minInsertions("aaaaaaaaaa") == 0  # repeated same char
Test Why
"zzazz" Validates already-palindrome input
"mbadm" Confirms example behavior
"leetcode" Confirms larger insertion count
"a" Tests smallest valid input
"aa" Tests simple palindrome
"ab" Tests single insertion case
"abc" Tests unique characters
"abcd" Tests increasing asymmetry
"race" Tests moderate insertion count
"abcba" Tests odd-length palindrome
"abccba" Tests even-length palindrome
"banana" Tests repeated characters
"google" Tests non-trivial repeated letters
"abcdefghijklmnopqrstuvwxyz" Stress test for many insertions
"aaaaaaaaaa" Tests repeated identical characters

Edge Cases

Single Character String

A string of length 1 is always a palindrome because it reads the same forward and backward. A naive implementation might accidentally overcount insertions if it does not handle trivial base cases correctly. Our implementation naturally handles this because the longest palindromic subsequence is the character itself, producing:

1 - 1 = 0

Already Palindromic String

Inputs such as "racecar" or "zzazz" should return 0. Some implementations mistakenly insert characters unnecessarily because they only examine local mismatches. Since our solution computes the global longest palindromic subsequence, the entire string becomes the subsequence, producing no insertions.

Completely Non-Palindromic Structure

Strings like "abcd" contain no repeated characters and have very weak symmetry. A naive greedy strategy may fail because choosing insertions locally can produce suboptimal results. Our dynamic programming method evaluates all subsequence possibilities and correctly determines that:

LPS = 1

therefore:

4 - 1 = 3

insertions are required.

Repeated Characters with Multiple Choices

Strings like "banana" are tricky because several valid palindromic subsequences exist. A greedy approach may choose a locally attractive match and miss the optimal answer. Dynamic programming avoids this issue by exploring every prefix combination and always preserving the globally best subsequence length.