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];
    }
};