101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 3 main approaches to solve this problem:

  1. Dynamic Programming with Longest Palindromic Subsequence - Complex approach
  2. Direct Dynamic Programming Approach - Complex approach
  3. Recursive Approach with Memoization - Complex approach

Approach 1: Dynamic Programming with Longest Palindromic Subsequence

The key insight for solving this problem is to find the longest palindromic subsequence (LPS) of the string. Once we know the LPS, the minimum number of insertions needed is simply the length of the string minus the length of the LPS.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. A palindromic subsequence is a subsequence that is also a palindrome.

For example, if the string is "leetcode", one of its palindromic subsequences is "ee", which has a length of 2. The minimum number of insertions needed would be 8 - 2 = 6. However, the longest palindromic subsequence is "ece" with length 3, so the minimum number of insertions needed is 8 - 3 = 5.

Algorithm:

  1. Define a function to find the longest palindromic subsequence (LPS) of the string using dynamic programming.
  2. Initialize a 2D DP table where dp[i][j] represents the length of the LPS of the substring s[i...j].
  3. For the base case, dp[i][i] = 1 for all i (a single character is a palindrome of length 1).
  4. For substrings of length 2 or more, if s[i] == s[j], then dp[i][j] = dp[i+1][j-1] + 2 (add the matching characters to the LPS).
  5. Otherwise, dp[i][j] = max(dp[i+1][j], dp[i][j-1]) (take the maximum of the LPS without the first character or without the last character).
  6. After filling the DP table, dp[0][n-1] gives the length of the LPS of the entire string.
  7. The minimum number of insertions needed is n - dp[0][n-1].

Time Complexity:

O(n²)

Where n is the length of the string. We need to fill a 2D DP table of size n×n.

Space Complexity:

O(n²)

We need a 2D DP table of size n×n to store the length of the LPS for each substring.

Approach 2: Direct Dynamic Programming Approach

Instead of finding the longest palindromic subsequence first, we can directly compute the minimum number of insertions needed using dynamic programming.

Let's define dp[i][j] as the minimum number of insertions needed to make the substring s[i...j] a palindrome.

For the base case, dp[i][i] = 0 for all i (a single character is already a palindrome, so no insertions are needed).

For substrings of length 2 or more, if s[i] == s[j], then dp[i][j] = dp[i+1][j-1] (no additional insertions needed for the matching characters).

Otherwise, dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1 (take the minimum of the insertions needed without the first character or without the last character, plus one for the character we need to insert).

Algorithm:

  1. Initialize a 2D DP table where dp[i][j] represents the minimum number of insertions needed to make the substring s[i...j] a palindrome.
  2. For the base case, dp[i][i] = 0 for all i (a single character is already a palindrome).
  3. For substrings of length 2, if s[i] == s[i+1], then dp[i][i+1] = 0, otherwise dp[i][i+1] = 1.
  4. For substrings of length 3 or more, if s[i] == s[j], then dp[i][j] = dp[i+1][j-1].
  5. Otherwise, dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1.
  6. After filling the DP table, dp[0][n-1] gives the minimum number of insertions needed for the entire string.

Time Complexity:

O(n²)

Where n is the length of the string. We need to fill a 2D DP table of size n×n.

Space Complexity:

O(n²)

We need a 2D DP table of size n×n to store the minimum number of insertions for each substring.

Approach 3: Recursive Approach with Memoization

We can also solve this problem using a recursive approach with memoization. The idea is to define a recursive function that computes the minimum number of insertions needed for a substring.

Let's define a function minInsertions(s, i, j) that returns the minimum number of insertions needed to make the substring s[i...j] a palindrome.

The base cases are:

  • If i > j, return 0 (empty string is a palindrome).
  • If i == j, return 0 (single character is a palindrome).

For the recursive case, if s[i] == s[j], then minInsertions(s, i, j) = minInsertions(s, i+1, j-1).

Otherwise, minInsertions(s, i, j) = min(minInsertions(s, i+1, j), minInsertions(s, i, j-1)) + 1.

Algorithm:

  1. Define a recursive function minInsertions(s, i, j) that returns the minimum number of insertions needed to make the substring s[i...j] a palindrome.
  2. Use memoization to avoid recomputing the same subproblems.
  3. For the base cases, if i >= j, return 0.
  4. For the recursive case, if s[i] == s[j], then minInsertions(s, i, j) = minInsertions(s, i+1, j-1).
  5. Otherwise, minInsertions(s, i, j) = min(minInsertions(s, i+1, j), minInsertions(s, i, j-1)) + 1.
  6. Call minInsertions(s, 0, n-1) to get the minimum number of insertions needed for the entire string.

Time Complexity:

O(n²)

Where n is the length of the string. With memoization, each subproblem is computed only once, and there are O(n²) possible subproblems.

Space Complexity:

O(n²)

We need to store the results of O(n²) subproblems in the memoization table, plus the recursion stack which can go up to O(n) in the worst case.

Pseudocode

solution.pseudo
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
function minInsertions(s):
    n = length of s
 
    // Find the longest palindromic subsequence
    function lps(s):
        n = length of s
        dp = 2D array of size n×n, initialized with 0s
 
        // Base case: single characters are palindromes of length 1
        for i from 0 to n-1:
            dp[i][i] = 1
 
        // Fill the DP table for substrings of length 2 or more
        for len from 2 to n:
            for i from 0 to n-len:
                j = i + len - 1
 
                if s[i] == s[j]:
                    dp[i][j] = dp[i+1][j-1] + 2
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])
 
        return dp[0][n-1]
 
    // The minimum number of insertions is the length of the string minus the length of the LPS
    return n - lps(s)
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone