1312. Minimum Insertion Steps to Make a String Palindrome
Intuition\n Describe your first thoughts on how to solve this problem. \nTo make a string palindrome, we need to insert characters in such a way that the result
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo make a string palindrome, we need to insert characters in such a way that the resulting string reads the same backward as well as forward. We can approach this problem using dynamic programming. The intuition is to determine the minimum number of insertions required to make substrings of the given string palindrome.\nIf we go for recursion, the Prgram will end in a **Memory Limit Exceeded** issue, which is due to the high no. of recursive calls. So, it is better to use DP.\n\nRecursive Solution: (MEMORY LIMIT EXCEEDED)\n```C++ []\nclass Solution {\npublic:\n    int minInsertionsRecursive(string s, int start, int end) {\n        // Base cases\n        if (start >= end) {\n            return 0;\n        }\n        if (s[start] == s[end]) {\n            return minInsertionsRecursive(s, start + 1, end - 1);\n        }\n        \n        // Recursive cases\n        int option1 = minInsertionsRecursive(s, start + 1, end) + 1;\n        int option2 = minInsertionsRecursive(s, start, end - 1) + 1;\n        \n        return min(option1, option2);\n    }\n\n    int minInsertions(string s) {\n        return minInsertionsRecursive(s, 0, s.length() - 1);\n    }\n};\n```\nTime Complexity of Recurive Approach is exponential -> O(2^n).\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Initialize the dp vector**: Create a vector dp of size n (length of the input string). This vector will store the minimum number of insertions required to make the substring from index i to index j a palindrome.\n2. **Iterate through the string**: Start iterating through the string from the second last character to the first character (in reverse order). For each character at index i, iterate through all the characters at indices j greater than i.\n3. **Check if characters at indices i and j are equal**: If the characters at indices i and j are equal, it means that they can form a palindrome without any additional insertions. In this case, set dp[j] to the value of dp[j-1] (which is the value of dp[j] in the previous iteration).\n4. **If characters at indices i and j are not equal**: If the characters at indices i and j are not equal, it means that at least one insertion is required to make the substring from index i to index j a palindrome. In this case, set dp[j] to the minimum of dp[j] and dp[j-1] plus 1.\n5. **Store the previous value of dp[j]**: To use the value of dp[j] in the previous iteration, store it in a variable prev before updating dp[j].\n6. **Return the minimum number of insertions**: After iterating through the entire string, the value of dp[n-1] will store the minimum number of insertions required to make the entire string a palindrome. Return this value as the final result.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ --> \n    O(n^2), where n is the length of the string.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    O(n), because we use an additional array dp of size n.\n\n# Code\n```\nclass Solution {\npublic:\n    int minInsertions(string s) {\n        int n = s.length();\n        vector<int> dp(n);\n        for (int i = n - 2; i >= 0; i--) {\n            int prev = 0;\n            for (int j = i + 1; j < n; j++) {\n                int temp = dp[j];\n                if (s[i] == s[j]) {\n                    dp[j] = prev;\n                } else {\n                    dp[j] = min(dp[j], dp[j-1]) + 1;\n                }\n                prev = temp;\n            }\n        }\n        return dp[n-1];\n    }\n};\n```
['String', 'Dynamic Programming', 'Recursion', 'C++']