47. Minimum Insertion Steps to Make a String Palindrome

Given a string s. In one step you can insert any character at any index of the string.

Return the minimum number of steps to make s palindrome.

A Palindrome String is one that reads the same backward as well as forward.

Example 1:

Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we don't need any insertions.

Example 2:

Input: s = "mbadm"
Output: 2
Explanation: String can be "mbdadbm" or "mdbabdm".

Example 3:

Input: s = "leetcode"
Output: 5
Explanation: Inserting 5 characters the string becomes "leetcodocteel".

Example 4:

Input: s = "g"
Output: 0

Example 5:

Input: s = "no"
Output: 1

Solution:(Finding Longest Palindromic Subsequence)

class Solution
{
public:
    int longestPalinSubstring(string s)
    {
        int n = s.length();

        vector<vector<int>> dp(n, vector<int>(n, 0));

        for (int i = 0; i < n; i++)
        {
            dp[i][i] = 1;
        }

        for (int i = 0; i < n - 1; i++)
        {
            if (s[i] == s[i + 1])
            {
                dp[i][i + 1] = 2;
            }
            else
            {
                dp[i][i + 1] = 1;
            }
        }

        for (int k = 3; k <= n; k++)
        {

            for (int i = 0; i <= n - k; i++)
            {

                if (s[i] == s[i + k - 1])
                {
                    dp[i][i + k - 1] = dp[i + 1][i + k - 2] + 2;
                }
                else
                {
                    dp[i][i + k - 1] = max(dp[i][i + k - 2], dp[i + 1][i + k - 1]);
                }
            }
        }

        return dp[0][n - 1];
    }

    int minInsertions(string s)
    {
        int maxLen = longestPalinSubstring(s);

        return s.length() - maxLen;
    }
};