Ex-Amazon explains a solution with a video, Python, JavaScript, Java and C++
My youtube channel - KeetCode(Ex-Amazon)\nI create 155 videos for leetcode questions as of April 24, 2023. I believe my channel helps you prepare for the coming
# My youtube channel - KeetCode(Ex-Amazon)\nI create 155 videos for leetcode questions as of April 24, 2023. I believe my channel helps you prepare for the coming technical interviews. Please subscribe my channel!\n\n### Please subscribe my channel - KeetCode(Ex-Amazon) from here.\n\n**I created a video for this question. I believe you can understand easily with visualization.** \n\n**My youtube channel - KeetCode(Ex-Amazon)**\nThere is my channel link under picture in LeetCode profile.\nhttps://leetcode.com/niits/\n\n![FotoJet (57).jpg](https://assets.leetcode.com/users/images/2154d840-dc22-454b-9993-09603e41de4c_1682286305.0137026.jpeg)\n\n\n# Intuition\nUse 1D dynamic programming to store minimum steps\n\n# Approach\n1. Get the length of the input string s and store it in a variable n.\n\n2. Create a list dp of length n filled with zeros to store the dynamic programming values.\n\n3. Loop through the indices of the string s from n - 2 to 0 in reverse order using for i in range(n - 2, -1, -1):.\n\n4. Inside the outer loop, initialize a variable prev to 0 to keep track of the previous dynamic programming value.\n\n5. Loop through the indices of the string s from i + 1 to n using for j in range(i + 1, n):.\n\n6. Inside the inner loop, store the current dynamic programming value in a temporary variable temp for future reference.\n\n7. Check if the characters at indices i and j in the string s are the same using if s[i] == s[j]:.\n\n8. If the characters are the same, update the dynamic programming value at index j in the dp list with the previous dynamic programming value prev.\n\n9. If the characters are different, update the dynamic programming value at index j in the dp list with the minimum of the dynamic programming values at index j and j-1 in the dp list, incremented by 1.\n\n10. Update the prev variable with the temporary variable temp.\n\n11. After the inner loop completes, the dynamic programming values in the dp list represent the minimum number of insertions needed to make s a palindrome.\n\n12. Return the dynamic programming value at index n-1 in the dp list as the final result. This represents the minimum number of insertions needed to make the entire string s a palindrome.\n\n\n---\n\n\n**If you don\'t understand the algorithm, let\'s check my video solution.\nThere is my channel link under picture in LeetCode profile.**\nhttps://leetcode.com/niits/\n\n\n---\n\n# Complexity\n- Time complexity: O(n^2)\nn is the length of the input string \'s\'. This is because there are two nested loops. The outer loop runs from n-2 to 0, and the inner loop runs from i+1 to n-1. In the worst case, the inner loop iterates n-1 times for each value of i, resulting in a total of (n-2) + (n-3) + ... + 1 = n(n-1)/2 iterations. Therefore, the overall time complexity is O(n^2).\n\n- Space complexity: O(n)\nn is the length of the input string \'s\'. This is because the code uses an array \'dp\' of size n to store the minimum number of insertions required at each position in \'s\'. Hence, the space complexity is linear with respect to the length of the input string.\n\n# Python\n```\nclass Solution:\n    def minInsertions(self, s: str) -> int:\n        n = len(s)\n        dp = [0] * n\n\n        for i in range(n - 2, -1, -1):\n            prev = 0\n\n            for j in range(i + 1, n):\n                temp = dp[j]\n\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        return dp[n-1]\n```\n# JavaScript\n```\n/**\n * @param {string} s\n * @return {number}\n */\nvar minInsertions = function(s) {\n    const n = s.length;\n    const dp = new Array(n).fill(0);\n\n    for (let i = n - 2; i >= 0; i--) {\n        let prev = 0;\n\n        for (let j = i + 1; j < n; j++) {\n            const temp = dp[j];\n\n            if (s[i] === s[j]) {\n                dp[j] = prev;\n            } else {\n                dp[j] = Math.min(dp[j], dp[j-1]) + 1;\n            }\n\n            prev = temp;\n        }\n    }\n\n    return dp[n-1];    \n};\n```\n# Java\n```\nclass Solution {\n    public int minInsertions(String s) {\n        int n = s.length();\n        int[] dp = new int[n];\n\n        for (int i = n - 2; i >= 0; i--) {\n            int prev = 0;\n\n            for (int j = i + 1; j < n; j++) {\n                int temp = dp[j];\n\n                if (s.charAt(i) == s.charAt(j)) {\n                    dp[j] = prev;\n                } else {\n                    dp[j] = Math.min(dp[j], dp[j-1]) + 1;\n                }\n\n                prev = temp;\n            }\n        }\n\n        return dp[n-1];        \n    }\n}\n```\n# C++\n```\nclass Solution {\npublic:\n    int minInsertions(string s) {\n        int n = s.length();\n        vector<int> dp(n, 0);\n\n        for (int i = n - 2; i >= 0; i--) {\n            int prev = 0;\n\n            for (int j = i + 1; j < n; j++) {\n                int temp = dp[j];\n\n                if (s[i] == s[j]) {\n                    dp[j] = prev;\n                } else {\n                    dp[j] = min(dp[j], dp[j-1]) + 1;\n                }\n\n                prev = temp;\n            }\n        }\n\n        return dp[n-1];        \n    }\n};\n```
['C++', 'Java', 'Python3', 'JavaScript']