DEV Community

Miss Pooja Anilkumar Patel
Miss Pooja Anilkumar Patel

Posted on

1312. Leetcode Solution in cpp

class Solution {
public:
    int minInsertions(string s) {
        int n = s.length();
        vector<int> dp(n);
        for (int i = n - 2; i >= 0; i--) {
            int prev = 0;
            for (int j = i + 1; j < n; j++) {
                int temp = dp[j];
                if (s[i] == s[j]) {
                    dp[j] = prev;
                } else {
                    dp[j] = min(dp[j], dp[j-1]) + 1;
                }
                prev = temp;
            }
        }
        return dp[n-1];
    }
};
Enter fullscreen mode Exit fullscreen mode

leetcode

challenge

Here is the link for the problem:
https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/

Top comments (0)