content: /*
      Given a string, find the minimum number of insertions needed to make it a palindrome.
  
      Sample Input: "abcde"
      Sample Output: 4
      Explanation: The minimum insertions required are 'edcb' -> "abcdecb", resulting in a palindrome.
  
      Approach:
      We can solve this problem using dynamic programming.
      Let's define a 2D table, dp, where dp[i][j] represents the minimum number of insertions needed to make the substring from index i to j a palindrome.
      If the characters at indices i and j are equal, then dp[i][j] = dp[i+1][j-1].
      Otherwise, we have two options:
          1. Insert the character at index i at the end, i.e., dp[i][j] = dp[i][j-1] + 1.
          2. Insert the character at index j at the beginning, i.e., dp[i][j] = dp[i+1][j] + 1.
      We take the minimum of these two options as the minimum number of insertions required for the substring from index i to j.
      Finally, the minimum number of insertions needed for the entire string is dp[0][n-1], where n is the length of the string.
  
      Time complexity: O(n^2)
      Space complexity: O(n^2)
  */
  
  public class PalindromeInsertion {
      public static int findMinInsertions(String s) {
          int n = s.length();
          int[][] dp = new int[n][n];
  
          for (int len = 2; len <= n; len++) {
              for (int i = 0; i <= n - len; i++) {
                  int j = i + len - 1;
                  if (s.charAt(i) == s.charAt(j))
                      dp[i][j] = dp[i + 1][j - 1];
                  else
                      dp[i][j] = Math.min(dp[i][j - 1], dp[i + 1][j]) + 1;
              }
          }
  
          return dp[0][n - 1];
      }
  
      public static void main(String[] args) {
          String input = "abcde";
          int minInsertions = findMinInsertions(input);
          System.out.println("Minimum insertions required: " + minInsertions);
      }
  }
  