LPS Based Approach 💯🔥|  LCS Variation DP 🚀✅
IntuitionTo make a string a palindrome, we need to insert characters into the string. The goal is to find the minimum number of insertions required.The key insi
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
To make a string a palindrome, we need to insert characters into the string. The goal is to find the minimum number of insertions required.

The key insight here is that the more of the string that is already a palindrome, the fewer insertions are needed. If we can find the Longest Palindromic Subsequence (LPS), then the remaining characters (those not part of the LPS) will need to be inserted in order to form a complete palindrome.
# Approach
<!-- Describe your approach to solving the problem. -->
1. **Reverse the String**:  
   Given a string `s`, we create a reversed version of the string `t`. The reason we reverse the string is because the **Longest Common Subsequence (LCS)** between the original string `s` and its reversed string `t` will give us the **Longest Palindromic Subsequence (LPS)** of `s`. This works because any sequence of characters that matches in both `s` and `t` is a palindromic subsequence.

2. **Compute the Longest Common Subsequence (LCS)**:  
   We then compute the **LCS** between `s` and `t`. The **LCS** is the longest subsequence that appears in both strings. In our case, this will be the longest palindromic subsequence of `s`.

3. **Calculate Minimum Insertions**:  
   After constructing the DP table, the value at `dp[n][n]` (where `n` is the length of `s`) will give us the length of the LPS of `s`


   *Formulae :* `Minimum Insertion` = `n` - `LPS`
   
# Complexity
- Time complexity: $$O(n^2)$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $$O(n^2)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```java []
class Solution {
    public int minInsertions(String s) {
        String t = new StringBuilder(s).reverse().toString();
        int n = s.length();
        int[][]dp = new int[n + 1][n + 1];
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                }
                else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return n - dp[n][n];
    }
}
```
['Dynamic Programming', 'Java']