Minimum Insertion Steps to Make a String Palindrome | 90% Faster | Simplest Approach | DP
Intuition\n Describe your first thoughts on how to solve this problem. \nWe need to find the minimum insertions required to make a string palindrome. Let us kee
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe need to find the minimum insertions required to make a string palindrome. Let us keep the \u201Cminimum\u201D criteria aside and think, how can we make any given string palindrome by inserting characters?\n\nThe easiest way is to add the reverse of the string at the back of the original string. This will make any string palindrome.\n\nHere the number of characters inserted will be equal to n (length of the string). This is the maximum number of characters we can insert to make strings palindrome.\n\nThe problem states us to find the minimum of insertions. Let us try to figure it out:\n\nTo minimize the insertions, we will first try to refrain from adding those characters again which are already making the given string palindrome. For the given example, \u201Caaa\u201D, \u201Caba\u201D,\u201Daca\u201D, any of these are themselves palindromic components of the string. We can take any of them( as all are of equal length) and keep them intact. (let\u2019s say \u201Caaa\u201D).\n\nNow, there are two characters(\u2018b\u2019 and \u2018c\u2019) remaining which prevent the string from being a palindrome. We can reverse their order and add them to the string to make the entire string palindrome.\n\nWe can do this by taking some other components (like \u201Caca\u201D) as well. \n\nIn order to minimize the insertions, we need to find the length of the longest palindromic component or in other words, the longest palindromic subsequence.\n\nMinimum Insertion required = n(length of the string) \u2013 length of longest palindromic subsequence.\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nThe algorithm is stated as follows:\n\nWe are given a string (say s), make a copy of it and store it( say string t).\nReverse the original string s.\nFind the longest common subsequence as in problem(1143. Longest Common Subsequence).\n\n\n# Complexity\n- Time complexity:\n- beat 90% of the user\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n- beat 98% of the user\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def minInsertions(self, s: str) -> int:\n        if s == s[::-1]:\n            return 0\n        n = len(s)\n        return n - self.longestPalindromeSubseq(s)\n        \n\n    def longestPalindromeSubseq(self, s: str) -> int:\n        t = s\n        s = s[::-1]\n        \n        n = len(s)\n    \n        prev = [0] * (n + 1)\n        cur = [0] * (n + 1)\n        for ind1 in range(1, n + 1):\n            for ind2 in range(1, n + 1):\n                if t[ind1 - 1] == s[ind2 - 1]:\n                    # If the characters match, increment LCS length by 1\n                    cur[ind2] = 1 + prev[ind2 - 1]\n                else:\n                    # If the characters do not match, take the maximum of LCS\n                    # by excluding one character from s1 or s2\n                    cur[ind2] = max(prev[ind2], cur[ind2 - 1])\n        \n            # Update \'prev\' to be the same as \'cur\' for the next iteration\n            prev = cur[:]\n\n        # The value in \'prev[m]\' represents the length of the Longest Common Subsequence\n        return prev[n]\n        \n```
['Python3']