Untitled
unknown
c_cpp
21 days ago
777 B
7
Indexable
int findMinimumDeletions(string p) { int n = p.length(); vector<vector<int>> dp(n, vector<int>(n, 0)); // Base case: single character needs 1 operation for (int i = 0; i < n; i++) dp[i][i] = 1; // Build for substrings of length > 1 for (int len = 2; len <= n; len++) { for (int i = 0; i <= n - len; i++) { int j = i + len - 1; dp[i][j] = 1 + dp[i + 1][j]; // remove p[i] alone for (int k = i + 1; k <= j; k++) { if (p[i] == p[k]) { int left = (k - 1 >= i + 1) ? dp[i + 1][k - 1] : 0; int right = dp[k][j]; dp[i][j] = min(dp[i][j], left + right); } } } } return dp[0][n - 1]; }
Editor is loading...
Leave a Comment