<p>Given a string <code>s</code>. In one step you can insert any character at any index of the string.</p>

<p>Return <em>the minimum number of steps</em> to make <code>s</code>&nbsp;palindrome.</p>

<p>A&nbsp;<b>Palindrome String</b>&nbsp;is one that reads the same backward as well as forward.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;zzazz&quot;
<strong>Output:</strong> 0
<strong>Explanation:</strong> The string &quot;zzazz&quot; is already palindrome we do not need any insertions.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;mbadm&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> String can be &quot;mbdadbm&quot; or &quot;mdbabdm&quot;.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;leetcode&quot;
<strong>Output:</strong> 5
<strong>Explanation:</strong> Inserting 5 characters the string becomes &quot;leetcodocteel&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 500</code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

# # Tabulation
# We need to find min insertions to make a string palindrome = len(s) - len(Longest palindrome Subsequence)

class Solution:
    def minInsertions(self, s: str) -> int:
        # we need to find the longest common subsequence palindrome

        n=len(s)
        s1=s
        s2=s[::-1] # reverse the string S and we find the Longest Common Subsequence(LCS) , then we get a palindrome(reverse of a string and the string itself is same)
        n1 = len(s1)
        n2 = len(s2)
        dp = [[-1 for i in range(n2 + 1)] for j in range(n1 + 1)]

        # base case after shifting of index -1 to 0, ie., {-1,0,1,2,3,4,5,.....} -> {0,1,2,3,4,5,6.....}
        for i in range(n1 + 1):
            dp[i][0] = 0
        for j in range(n2 + 1):
            dp[0][j] = 0

        for ind1 in range(1, n1 + 1):
            for ind2 in range(1, n2 + 1):
                # match case
                if (s1[ind1 - 1] == s2[ind2 - 1]):  # as we are shifting the index -1 to 0
                    dp[ind1][ind2] = (1 + dp[ind1 - 1][ind2 - 1])  # add 1 to answer and move each of the two pointers

                # not match (Explore all possiblity by moving each ind1, ind2 separetely )
                else:
                    move_ind1 = 0 + dp[ind1 - 1][ind2]  # 0 as we have no match
                    move_ind2 = 0 + dp[ind1][ind2 - 1]

                    dp[ind1][ind2] = max(move_ind1, move_ind2)

        return n-dp[n1][n2] # dp[n1][n2] contains the string having Longest palindrome Subsequence length
         

# https://www.youtube.com/watch?v=xPBLEj41rFU
20779