✔3 STEPS DP Sol | Asked by AMAZON-GOOGLE-UBER || EXPLANATION & COMPLEXITIES👈
EXPLANATION :-\n1. THIS PROBLEM IS MAINLY EXTENSION OF LPS(Longest Palindromic Subsequence).\n2. MOREOVER, THIS IS A DITTO COPY OF A CLASSICAL QUESTION OF DP KN
* ## EXPLANATION :-\n1. **`THIS PROBLEM IS MAINLY EXTENSION OF LPS(Longest Palindromic Subsequence).`**\n2. **`MOREOVER, THIS IS A DITTO COPY OF A CLASSICAL QUESTION OF DP KNOWN AS MINIMUM NUMBER OF DELETION TO MAKE A STRING PALINDROME.`**\n3. **`IDEA : In this problem we just have to find LPS of the given string and subtract the LPS length from given string len !!`\n    `BECAUSE, MINIMUM NUMBER OF INSERTIONS IS EQUAL TO MINIMUM NUMBER OF DELETION IN A STRING TO MAKE IT PALINDROME..`\n    `ATLAST, HOW THIS QUESTION IS A EXTENSION OF LPS (Longest Palindromic Subsequence). SO, THE BASIC IDEA IS, IF WE FIND OUT LPS OF THE TWO SAME STRING`.\n    `AND IF THE LONGEST COMMON(SIMILAR) CHARACTERS ARE MORE \u2B06, THAT MEANS THERE WILL BE LEAST DISIMILAR CHARACTERS \u2B07. HENCE, WE HAVE TO DELETE OR INSERT LEAST`\n    `CHARACTERS IN A STRING TO MAKE A STRING PALINDROME!`**\n4. **`IN A SIMPLE WORDS : LONGEST PALINDROMIC SUBSEQUENCE(LPS) IS INVERSELY PROPORTIONAL TO NUMBER OF DELETIONS(OR NUMBER OF INSERTIONS)`**\n```\n\t\t\t\t\t\t  1   \n    LPS \u2B06  \u221D      -------------------\n\t\t\t\t   NO. OF DELETIONS \u2B07\t\n```\t\t\t\n```\nclass Solution {\npublic:\n    int minInsertions(string s1) {\n        int n = s1.size();\n        string s2 = s1;\n        reverse(s2.begin(), s2.end());\n        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));\n        for(int i = 1; i <= n; ++i){\n            for(int j = 1; j <= n; ++j){\n                if(s1[i - 1] == s2[j - 1])\n                    dp[i][j] = 1 + dp[i - 1][j - 1];                    // FIRST STEP\n                else\n                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);         // SECOND STEP\n            }\n        }\n        int lenLPS = dp[n][n];\n        return n - lenLPS;                                              // THIRD STEP\n    }\n};\n```\n**TIME COMPLEXITY : `O(n^2) == O(n * n)`, Where, n = size of str1 & str2** \n**SPACE COMPLEXITY : `O(n * n)`, For using 2D array Aux space**\n\nif you find any mistakes pls, drop a comment\nif it makes any sense don\'t forget to **Upvote**
['Dynamic Programming']