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.
1#include <stdio.h>
2#include <string.h>
3
4int minInsertions(char *s) {
5 int n = strlen(s);
6 int dp[n][n];
7 memset(dp, 0, sizeof(dp));
8 for (int len = 1; len < n; len++) {
9 for (int i = 0, j = len; j < n; i++, j++) {
10 if (s[i] == s[j]) {
11 dp[i][j] = dp[i+1][j-1];
12 } else {
13 dp[i][j] = 1 + ((dp[i+1][j] < dp[i][j-1]) ? dp[i+1][j] : dp[i][j-1]);
14 }
15 }
16 }
17 return dp[0][n-1];
18}
19
20int main() {
21 char s[] = "mbadm";
22 printf("%d\n", minInsertions(s));
23 return 0;
24}The function uses a 2D array dp where dp[i][j] represents the minimum insertions required to make the substring s[i...j] a palindrome. We iterate over increasing lengths of substrings and decide whether to skip or keep certain characters based on whether they match.
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.
1import java.util.Arrays;
2
3public class RecurMemo {
4 int[][] dp;
5
6 public int solve(String s, int left, int right) {
7 if (left >= right) return 0;
8 if (dp[left][right] != -1) return dp[left][right];
9 if (s.charAt(left) == s.charAt(right))
10 dp[left][right] = solve(s, left + 1, right - 1);
11 else
12 dp[left][right] = 1 + Math.min(solve(s, left + 1, right), solve(s, left, right - 1));
13 return dp[left][right];
14 }
15
16 public int minInsertions(String s) {
17 int n = s.length();
18 dp = new int[n][n];
19 for (int[] row : dp) Arrays.fill(row, -1);
20 return solve(s, 0, n - 1);
21 }
22
23 public static void main(String[] args) {
24 RecurMemo recurMemo = new RecurMemo();
25 System.out.println(recurMemo.minInsertions("mbadm"));
26 }
27}This Java solution uses a recursive approach with memoization, storing results in a 2D array initialized with -1. The recursion helps find the minimum insertion count efficiently.