Using LCS 🔥 C++🔥Simple Explanation 🔥Easy approach 🔥
PLEASE UPVOTE \uD83D\uDC4D\n# Approach\n- ##### To make a string s palindrome, we need to add characters to the string such that it becomes the same when read f
# **PLEASE UPVOTE \uD83D\uDC4D**\n# Approach\n- ##### To make a string s palindrome, we need to add characters to the string such that it becomes the same when read from both sides. \n- ##### The idea is to find the LCS between the original string s and its reverse string s\'. The length of LCS will give us the number of characters that are already palindrome in s. We can subtract this length from the length of s to get the number of characters we need to add to make s palindrome.\n- ##### Let dp[i][j] be the length of the longest common subsequence between the first i characters of string A and the first j characters of string B. We can fill up the table using the following recurrence relation:\n    1. ##### If A[i-1] == B[j-1], then dp[i][j] = dp[i-1][j-1] + 1, because the ith and jth characters match and contribute to the LCS.\n    2. ##### If A[i-1] != B[j-1], then dp[i][j] = max(dp[i-1][j], dp[i][j-1]), because the ith and jth characters do not match and we have two options: either skip the ith character of A or skip the jth character of B.\n- ##### The final answer will be stored in dp[m][n], where m and n are the lengths of the input strings A and B, respectively.\n\n# Intuition\n- ##### The intuition behind using the LCS algorithm to find the minimum number of steps to make a string palindrome is based on the fact that a palindrome string is symmetric around its center.\n\n- ##### Let\'s consider an example string "abcd". To make it a palindrome, we can add characters "d", "c", "b" to the beginning of the string to get "dcbaabcd", which is a palindrome. Alternatively, we can add characters "a", "b", "c" to the end of the string to get "abcddcba", which is also a palindrome.\n\n- ##### In general, to make a string palindrome, we need to add characters to either the beginning or the end of the string to make it symmetric around its center. The center of the string is the middle character(s) if the length of the string is odd, or the two middle characters if the length of the string is even.\n\n# Complexity\n- Time complexity: O(n^2)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n^2)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# **PLEASE UPVOTE \uD83D\uDC4D**\n# Code\n```\nclass Solution {\npublic:\n    int lcs(string t, string s, vector<vector<int>>&dp){\n        int n = s.size();\n        for(int i = 0; i <= n; i++){\n            for(int j = 0; j <= n; j++){\n                if(i == 0 || j == 0)\n                dp[i][j] = 0;\n            }\n        }\n\n        for(int i = 1; i <= n; i++){\n            for(int j = 1; j <= n; j++){\n                if(s[i-1] == t[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                }\n            }\n        }\n        return dp[n][n];\n    }\n    \n    int minInsertions(string s) {\n        string t = s;\n        reverse(t.begin(),t.end());\n        int n = s.size();\n        vector<vector<int>>dp(n+1,vector<int>(n+1,0));\n        return n - lcs(s,t,dp);\n    }\n};\n```\n![e2515d84-99cf-4499-80fb-fe458e1bbae2_1678932606.8004954.png](https://assets.leetcode.com/users/images/13c32ead-4eb5-472d-8301-8e78d3bcc3c5_1682123350.7417476.png)\n\n
['String', 'Dynamic Programming', 'C++']