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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
/**
 * Find the minimum number of insertions needed to make a string a palindrome.
 * Dynamic Programming with Longest Palindromic Subsequence approach.
 *
 * @param {string} s - The input string
 * @return {number} - The minimum number of insertions needed
 */
function minInsertions(s) {
  const n = s.length;
 
  // Find the longest palindromic subsequence
  function lps(s) {
    const n = s.length;
    const dp = Array(n).fill().map(() => Array(n).fill(0));
 
    // Base case: single characters are palindromes of length 1
    for (let i = 0; i < n; i++) {
      dp[i][i] = 1;
    }
 
    // Fill the DP table for substrings of length 2 or more
    for (let len = 2; len <= n; len++) {
      for (let i = 0; i <= n - len; i++) {
        const j = i + len - 1;
 
        if (s[i] === s[j]) {
          dp[i][j] = dp[i + 1][j - 1] + 2;
        } else {
          dp[i][j] = Math.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);
}
 
/**
 * Find the minimum number of insertions needed to make a string a palindrome.
 * Direct Dynamic Programming approach.
 *
 * @param {string} s - The input string
 * @return {number} - The minimum number of insertions needed
 */
function minInsertionsDirect(s) {
  const n = s.length;
  const dp = Array(n).fill().map(() => Array(n).fill(0));
 
  // Fill the DP table for substrings of length 2 or more
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
 
      if (s[i] === s[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 dp[0][n - 1];
}
 
/**
 * Find the minimum number of insertions needed to make a string a palindrome.
 * Recursive approach with memoization.
 *
 * @param {string} s - The input string
 * @return {number} - The minimum number of insertions needed
 */
function minInsertionsRecursive(s) {
  const n = s.length;
  const memo = new Map();
 
  /**
   * Recursive function to find the minimum number of insertions.
   *
   * @param {number} i - Start index of the substring
   * @param {number} j - End index of the substring
   * @return {number} - Minimum number of insertions needed for the substring
   */
  function dp(i, j) {
    // Base cases
    if (i >= j) {
      return 0;
    }
 
    // Check if we've already computed this subproblem
    const key = `${i},${j}`;
    if (memo.has(key)) {
      return memo.get(key);
    }
 
    // Recursive cases
    let result;
    if (s[i] === s[j]) {
      result = dp(i + 1, j - 1);
    } else {
      result = Math.min(dp(i + 1, j), dp(i, j - 1)) + 1;
    }
 
    // Memoize and return
    memo.set(key, result);
    return result;
  }
 
  return dp(0, n - 1);
}
 
// Test cases
console.log(minInsertions("zzazz"));  // 0
console.log(minInsertions("mbadm"));  // 2
console.log(minInsertions("leetcode"));  // 5
 
console.log(minInsertionsDirect("zzazz"));  // 0
console.log(minInsertionsDirect("mbadm"));  // 2
console.log(minInsertionsDirect("leetcode"));  // 5
 
console.log(minInsertionsRecursive("zzazz"));  // 0
console.log(minInsertionsRecursive("mbadm"));  // 2
console.log(minInsertionsRecursive("leetcode"));  // 5