Lexicographically Smallest Palindrome by Minimum Insertions

Problem

Given a string s, find the palindrome that can be made by inserting the fewest number of characters (anywhere in the string). If there is more than one palindrome of minimum length, return the lexicographically smallest one.

Examples

Example 1

1
2
3


Input: s = "race"
Output: "ecarace"
Explanation: We can add three letters to make "ecarace". There are other palindromes of length 7, but "ecarace" is lex smallest.

Example 2

1
2
3


Input: s = "google"
Output: "elgoogle"
Explanation: Appending "elg" at the front gives the lex smallest palindrome of minimum length.

Solution

Method 1 – Dynamic Programming with Backtracking

Intuition

We use DP to compute the minimum number of insertions needed for every substring. To construct the lexicographically smallest palindrome, we backtrack from the DP table, always choosing the lex smaller character when there is a tie. All variable names like dp, i, j, and s refer to the DP table, substring indices, and the input string, respectively.

Approach

Let n be the length of s. Create a DP table dp[i][j] for the minimum insertions to make s[i..j] a palindrome.
Fill the table:

If s[i] == s[j], then dp[i][j] = dp[i+1][j-1].
Else, dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1.

To construct the answer, use a recursive or iterative backtracking process:

If s[i] == s[j], add s[i] to both ends and recurse on s[i+1..j-1].
If dp[i+1][j] < dp[i][j-1], add s[i] to both ends and recurse on s[i+1..j].
If dp[i+1][j] > dp[i][j-1], add s[j] to both ends and recurse on s[i..j-1].
If equal, pick the lexicographically smaller character.

Return the constructed palindrome.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution {
public:
  string minInsertPalindrome(string s) {
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int len = 2; len <= n; ++len) {
      for (int i = 0; i + len - 1 < n; ++i) {
        int j = i + len - 1;
        if (s[i] == s[j]) dp[i][j] = dp[i+1][j-1];
        else dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1;
      }
    }
    function<string(int,int)> build = [&](int i, int j) -> string {
      if (i > j) return "";
      if (i == j) return string(1, s[i]);
      if (s[i] == s[j]) return s[i] + build(i+1, j-1) + s[j];
      if (dp[i+1][j] < dp[i][j-1]) return s[i] + build(i+1, j) + s[i];
      if (dp[i+1][j] > dp[i][j-1]) return s[j] + build(i, j-1) + s[j];
      // Tie: pick lex smaller
      string left = s[i] + build(i+1, j) + s[i];
      string right = s[j] + build(i, j-1) + s[j];
      return min(left, right);
    };
    return build(0, n-1);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution {
  public String minInsertPalindrome(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    for (int len = 2; len <= n; ++len) {
      for (int i = 0; i + len - 1 < n; ++i) {
        int j = i + len - 1;
        if (s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i+1][j-1];
        else dp[i][j] = Math.min(dp[i+1][j], dp[i][j-1]) + 1;
      }
    }
    return build(s, dp, 0, n-1);
  }
  private String build(String s, int[][] dp, int i, int j) {
    if (i > j) return "";
    if (i == j) return s.substring(i, i+1);
    if (s.charAt(i) == s.charAt(j)) return s.charAt(i) + build(s, dp, i+1, j-1) + s.charAt(j);
    if (dp[i+1][j] < dp[i][j-1]) return s.charAt(i) + build(s, dp, i+1, j) + s.charAt(i);
    if (dp[i+1][j] > dp[i][j-1]) return s.charAt(j) + build(s, dp, i, j-1) + s.charAt(j);
    String left = s.charAt(i) + build(s, dp, i+1, j) + s.charAt(i);
    String right = s.charAt(j) + build(s, dp, i, j-1) + s.charAt(j);
    return left.compareTo(right) < 0 ? left : right;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


class Solution:
  def min_insert_palindrome(self, s: str) -> str:
    n = len(s)
    dp = [[0]*n for _ in range(n)]
    for length in range(2, n+1):
      for i in range(n-length+1):
        j = i + length - 1
        if s[i] == s[j]:
          dp[i][j] = dp[i+1][j-1]
        else:
          dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1
    from functools import lru_cache
    @lru_cache(maxsize=None)
    def build(i: int, j: int) -> str:
      if i > j:
        return ""
      if i == j:
        return s[i]
      if s[i] == s[j]:
        return s[i] + build(i+1, j-1) + s[j]
      if dp[i+1][j] < dp[i][j-1]:
        return s[i] + build(i+1, j) + s[i]
      if dp[i+1][j] > dp[i][j-1]:
        return s[j] + build(i, j-1) + s[j]
      left = s[i] + build(i+1, j) + s[i]
      right = s[j] + build(i, j-1) + s[j]
      return min(left, right)
    return build(0, n-1)

Complexity

⏰ Time complexity: O(n^2) for DP and backtracking, since each substring is processed once and the build step is memoized.
🧺 Space complexity: O(n^2) for the DP table and recursion/memoization.

Problem#

Examples#

Example 1#

Example 2#

Solution#

Method 1 – Dynamic Programming with Backtracking#

Intuition#

Approach#

Code#

Complexity#