Day 112 || Recursion > Memoization || Easiest Beginner Friendly Sol
NOTE - PLEASE READ INTUITION AND APPROACH FIRST THEN SEE THE CODE. YOU WILL DEFINITELY UNDERSTAND THE CODE LINE BY LINE AFTER SEEING THE APPROACH.\n\n# Intuitio
**NOTE - PLEASE READ INTUITION AND APPROACH FIRST THEN SEE THE CODE. YOU WILL DEFINITELY UNDERSTAND THE CODE LINE BY LINE AFTER SEEING THE APPROACH.**\n\n# Intuition of this Problem :\n**If you know how to solve Longest palindromic Subsequence then this problem is easy for you. For example s = "acdsddca" then longest palondromic subsequence is "acddca" i.e. of length 6. It means if we insert n - 6 = 8 - 6 = 2 character in this given string then this string is palindromic string. How?\n Earlier we have earlier string s = "acdsddca" now we need to add two more charater to amke this string palindromic i.e. new string s = "acdsddsdca"**\n\n516. Longest Palindromic Subsequence - https://leetcode.com/problems/longest-palindromic-subsequence/\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n\n# Code :\n```C++ []\n// Recursive approach - TLE\n//The time complexity of the longestPalindromeSubstring function is O(2^n) where n is the length of the input string s. This is because in the worst case, the function will make two recursive calls at each step, effectively creating a binary tree with 2^n nodes.\n//The space complexity of the algorithm is O(n) due to the recursive calls on the call stack. In the worst case, the call stack can grow to a depth of n, corresponding to the length of the input string s.\nclass Solution {\npublic:\n    int longestPalindromeSubstring(string& s, int i, int j) {\n        if (i > j)\n            return 0;\n        else if (i == j)\n            return 1;\n        else if (s[i] == s[j])\n            return 2 + longestPalindromeSubstring(s, i+1, j-1);\n        else\n            return max(longestPalindromeSubstring(s, i+1, j), longestPalindromeSubstring(s, i, j-1));\n    }\n    int minInsertions(string s) {\n        int n = s.length();\n        int minNumSteps = n - longestPalindromeSubstring(s, 0, n-1);\n        return minNumSteps;\n    }\n};\n```\n```C++ []\n// Memoization (top-down DP) - Accepted\n//The time complexity of the longestPalindromeSubstring function with memoization is O(n^2), where n is the length of the input string s. This is because the function can be visualized as filling in a diagonal strip in a 2D matrix of size n x n, and each entry is computed only once and stored in the memo table.\n//The space complexity of the algorithm is O(n^2) due to the memoization table. It requires a 2D array of size n x n to store the computed results.\nclass Solution {\npublic:\n    int longestPalindromeSubstring(string& s, int i, int j, vector<vector<int>>& memo) {\n        if (i > j)\n            return 0;\n        else if (i == j)\n            return 1;\n        else if (memo[i][j] != -1)\n            return memo[i][j];\n        else if (s[i] == s[j])\n            return memo[i][j] = 2 + longestPalindromeSubstring(s, i+1, j-1, memo);\n        else\n            return memo[i][j] = max(longestPalindromeSubstring(s, i+1, j, memo), longestPalindromeSubstring(s, i, j-1, memo));\n    }\n    int minInsertions(string s) {\n        int n = s.length();\n        vector<vector<int>> memo(n, vector<int>(n, -1));\n        int minNumSteps = n - longestPalindromeSubstring(s, 0, n-1, memo);\n        return minNumSteps;\n    }\n};\n```\n```C++ []\n// Tabulation (bottm-up DP) - coming soon\n```
['Recursion', 'Memoization', 'C++']