Longest common Subsequence extension....(Python3)
Intuition\n Describe your first thoughts on how to solve this problem. \nI literally donnot have any idea then i came up with brute force and it didnt worked\n#
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nI literally donnot have any idea then i came up with brute force and it didnt worked\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThis is just a longest common subsequence question just reverse the given string and then return the lenght minus the common subsequence length\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def minInsertions(self, s: str) -> int:\n        r=s[::-1]\n        n=len(r)\n        dp=[[0 for i in range(n+1)]for j in range(n+1)]\n        for i in range(1,len(dp)):\n            for j in range(1,len(dp[0])):\n                if(s[i-1]==r[j-1]):\n                    dp[i][j]=1+dp[i-1][j-1]\n                else:\n                    dp[i][j]=max(dp[i-1][j],dp[i][j-1])\n        return n-dp[n][n]\n        \n```
['Python3']