// 1312. Minimum Insertion Steps to Make a String Palindrome #include #include #include #include /* * given string 's'. in one step you can insert any character at any index of * the string. return the minimum number of steps to make 's' palindrome. a * palindrome string is one that reads the same backward as well as forward. */ int minInsertions(char *s) { int n = strlen(s); int **dp = malloc(n * sizeof(int)); for (int i = 0; i < n; i++) dp[i] = calloc(n, sizeof(int)); for (int i = 0; i < n; i++) dp[i][i] = 1; for (int i = 0; i < n - 1; i++) { if (s[i] == s[i + 1]) dp[i][i + 1] = 2; else dp[i][i + 1] = 1; } for (int len = 2; len <= n; len++) { for (int i = 0; i <= n - len; i++) { int j = i + len - 1; if (s[i] == s[j]) dp[i][j] = 2 + dp[i + 1][j - 1]; else dp[i][j] = fmax(dp[i + 1][j], dp[i][j - 1]); } } int ans = n - dp[0][n - 1]; for (int i = 0; i < n; i++) free(dp[i]); free(dp); return ans; } int main() { char s1[] = {"zzazz"}, s2[] = {"mbadm"}, s3[] = {"leetcode"}; printf("%d\n", minInsertions(s1)); // expect: 0; printf("%d\n", minInsertions(s2)); // expect: 2; printf("%d\n", minInsertions(s3)); // expect: 5; }