This approach utilizes dynamic programming to find the longest palindromic subsequence in the given string. The minimum number of insertions required is the difference between the length of the string and this subsequence. The idea is to consider characters from both ends of the string and make decisions accordingly using a DP table.
Time Complexity: O(n^2), where 'n' is the length of the string. This is due to the nested loops filling the DP table.
Space Complexity: O(n^2), as it uses a two-dimensional array for the DP table.
1public class MinInsertions {
2 public static int minInsertions(String s) {
3 int n = s.length();
4 int[][] dp = new int[n][n];
5 for (int len = 1; len < n; len++) {
6 for (int i = 0, j = len; j < n; i++, j++) {
7 if (s.charAt(i) == s.charAt(j)) {
8 dp[i][j] = dp[i+1][j-1];
9 } else {
10 dp[i][j] = 1 + Math.min(dp[i+1][j], dp[i][j-1]);
11 }
12 }
13 }
14 return dp[0][n-1];
15 }
16
17 public static void main(String[] args) {
18 System.out.println(minInsertions("mbadm"));
19 }
20}The Java solution uses a similar DP approach with a 2D array. The nested loops fill the DP table based on character matches from both ends.
This approach leverages a recursive function to explore all possibilities, but uses memoization to cache results of previously computed subproblems. This reduces redundant calculations.
Time Complexity: O(n^2)
Space Complexity: O(n^2) due to the memoization table.
1#include <stdio.h>
2#include <string.h>
3#define MAX 500
4
5int dp[MAX][MAX];
6
7int solve(char *s, int left, int right) {
8 if (left >= right)
9 return 0;
10 if (dp[left][right] != -1)
11 return dp[left][right];
12 if (s[left] == s[right])
13 dp[left][right] = solve(s, left + 1, right - 1);
14 else
15 dp[left][right] = 1 + (solve(s, left + 1, right) < solve(s, left, right - 1) ? solve(s, left + 1, right) : solve(s, left, right - 1));
16 return dp[left][right];
17}
18
19int minInsertions(char *s) {
20 memset(dp, -1, sizeof(dp));
21 return solve(s, 0, strlen(s) - 1);
22}
23
24int main() {
25 char s[] = "mbadm";
26 printf("%d\n", minInsertions(s));
27 return 0;
28}This C solution uses a recursive function solve which calculates the minimum insertions needed for a substring. It includes memoization to store intermediate results in a 2D array, avoiding redundant calculations.