Form a palindrome

Given a string, find the minimum number of characters to be inserted to convert it to a palindrome.

Examples :

Input: str = "abcd"
Output: 3
Explanation: Inserted character marked with bold characters in dcbabcd, here we need minimum three characters to make it palindrome.

Input: str = "aa"
Output: 0
Explanation: "aa" is already a palindrome.

Expected Time Complexity: O(n²)
Expected Auxiliary Space: O(n²)

Constraints:
1 ≤ |str| ≤ 500
str contains only lowercase alphabets.

Approach 01

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

class Solution {
public:
    int countMin(string str) {
        int n = str.length();
        std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));

        // Initialize the diagonal elements (single character palindromes)
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        // Fill the remaining elements of the dp array
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;

                // If characters at i and j are the same
                if (str[i] == str[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                }
                // If characters at i and j are different
                else {
                    dp[i][j] = std::max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }

        // The minimum number of deletions required
        return n - dp[0][n - 1];
    }
};

class Solution:
    def countMin(self, s: str) -> int:
        n = len(s)
        dp = [[0] * n for _ in range(n)]

        # Initialize the diagonal elements (single character palindromes)
        for i in range(n):
            dp[i][i] = 1

        # Fill the remaining elements of the dp array
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1

                # If characters at i and j are the same
                if s[i] == s[j]:
                    dp[i][j] = dp[i + 1][j - 1] + 2
                # If characters at i and j are different
                else:
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

        # The minimum number of deletions required
        return n - dp[0][n - 1]

Time Complexity

• Filling the DP Table:

  The function uses a dynamic programming table of size n x n, where n is the length of the string. To fill this table, there are two nested loops:

  • The outer loop iterates over the length of the substring (from 2 to n), which runs in \( O(n) \) time.
  • The inner loop iterates over all possible starting positions for substrings of the current length, which also runs in \( O(n) \) time.

  Thus, the overall time complexity for filling the DP table is \( O(n^2) \).

Space Complexity

• DP Table:

  The DP table is a 2D vector of size n x n, which requires \( O(n^2) \) space.

• Other Variables:

  Other variables such as n, i, j, and intermediate values used for computation take \( O(1) \) space.

• Overall Space Complexity:

  The overall space complexity is \( O(n^2) \) due to the DP table.