# Minimum steps to delete a string after repeated deletion of palindrome substrings

Given a string containing characters as integers only. We need to delete all character of this string in a minimum number of steps where in one step we can delete the substring which is a palindrome. After deleting a substring remaining parts are concatenated.
Examples:

```Input : s = “2553432”
Output : 2
We can delete all character of above string in
2 steps, first deleting the substring s[3, 5] “343”
and then remaining string completely  s[0, 3] “2552”

Input : s = “1234”
Output : 4
We can delete all character of above string in 4
steps only because each character need to be deleted
separately. No substring of length 2 is a palindrome
in above string.
```

We can solve this problem using Dynamic programming. Let dp[i][j] denotes the number of steps it takes to delete the substring s[i, j]. Each character will be deleted alone or as part of some substring so in the first case we will delete the character itself and call subproblem (i+1, j). In the second case we will iterate over all occurrence of the current character in right side, if K is the index of one such occurrence then the problem will reduce to two subproblems (i+1, K – 1) and (K+1, j). We can reach to this subproblem (i+1, K-1) because we can just delete the same character and call for mid substring. We need to take care of a case when first two characters are same in that case we can directly reduce to the subproblem (i+2, j)

So after above discussion of relation among subproblems, we can write dp relation as follows,

```dp[i][j] = min(1 + dp[i+1][j],
dp[i+1][K-1] + dp[K+1][j],  where s[i] == s[K]
1 + dp[i+2][j] )
```

Total time complexity of above solution is O(n^3)

## C++

br>
 `//  C++ program to find minimum step to delete a string ` `#include ` `using` `namespace` `std; ` ` `  `/* method returns minimum step for deleting the string, ` `   ``where in one step a palindrome is removed */` `int` `minStepToDeleteString(string str) ` `{ ` `    ``int` `N = str.length(); ` ` `  `    ``//  declare dp array and initialize it with 0s ` `    ``int` `dp[N + 1][N + 1]; ` `    ``for` `(``int` `i = 0; i <= N; i++) ` `        ``for` `(``int` `j = 0; j <= N; j++) ` `            ``dp[i][j] = 0; ` ` `  `    ``// loop for substring length we are considering ` `    ``for` `(``int` `len = 1; len <= N; len++) ` `    ``{ ` `        ``// loop with two variables i and j, denoting ` `        ``// starting and ending of substrings ` `        ``for` `(``int` `i = 0, j = len - 1; j < N; i++, j++) ` `        ``{ ` `            ``// If substring length is 1, then 1 step ` `            ``// will be needed ` `            ``if` `(len == 1) ` `                ``dp[i][j] = 1; ` `            ``else` `            ``{ ` `                ``// delete the ith char individually ` `                ``// and assign result for subproblem (i+1,j) ` `                ``dp[i][j] = 1 + dp[i + 1][j]; ` ` `  `                ``// if current and next char are same, ` `                ``// choose min from current and subproblem ` `                ``// (i+2,j) ` `                ``if` `(str[i] == str[i + 1]) ` `                    ``dp[i][j] = min(1 + dp[i + 2][j], dp[i][j]); ` ` `  `                ``/*  loop over all right characters and suppose ` `                    ``Kth char is same as ith character then ` `                    ``choose minimum from current and two ` `                    ``substring after ignoring ith and Kth char */` `                ``for` `(``int` `K = i + 2; K <= j; K++) ` `                    ``if` `(str[i] == str[K]) ` `                        ``dp[i][j] = min(dp[i+1][K-1] + dp[K+1][j], ` `                                                       ``dp[i][j]); ` `            ``} ` `        ``} ` `    ``} ` ` `  `    ``/* Uncomment below snippet to print actual dp tablex ` `    ``for (int i = 0; i < N; i++, cout << endl) ` `        ``for (int j = 0; j < N; j++) ` `            ``cout << dp[i][j] << " ";    */` ` `  `    ``return` `dp[N - 1]; ` `} ` ` `  `//  Driver code to test above methods ` `int` `main() ` `{ ` `    ``string str = ``"2553432"``; ` `    ``cout << minStepToDeleteString(str) << endl; ` `    ``return` `0; ` `} `

## Java

 `// Java program to find minimum step to  ` `// delete a string ` `public` `class` `GFG  ` `{                             ` `    ``/* method returns minimum step for deleting ` `       ``the string, where in one step a ` `       ``palindrome is removed ` `     ``*/` `    ``static` `int` `minStepToDeleteString(String str) { ` `        ``int` `N = str.length(); ` ` `  `        ``// declare dp array and initialize it with 0s ` `        ``int``[][] dp = ``new` `int``[N + ``1``][N + ``1``]; ` `        ``for` `(``int` `i = ``0``; i <= N; i++) ` `            ``for` `(``int` `j = ``0``; j <= N; j++) ` `                ``dp[i][j] = ``0``; ` ` `  `        ``// loop for substring length we are considering ` `        ``for` `(``int` `len = ``1``; len <= N; len++) { ` `             `  `            ``// loop with two variables i and j, denoting ` `            ``// starting and ending of substrings ` `            ``for` `(``int` `i = ``0``, j = len - ``1``; j < N; i++, j++) { ` `     `  `                ``// If substring length is 1, then 1 step ` `                ``// will be needed ` `                ``if` `(len == ``1``) ` `                    ``dp[i][j] = ``1``; ` `                     `  `                ``else` `{ ` `                    ``// delete the ith char individually ` `                    ``// and assign result for  ` `                    ``// subproblem (i+1,j) ` `                    ``dp[i][j] = ``1` `+ dp[i + ``1``][j]; ` ` `  `                    ``// if current and next char are same, ` `                    ``// choose min from current and  ` `                    ``// subproblem (i+2, j) ` `                    ``if` `(str.charAt(i) == str.charAt(i + ``1``)) ` `                        ``dp[i][j] = Math.min(``1` `+ dp[i + ``2``][j],  ` `                                               ``dp[i][j]); ` ` `  `                    ``/* loop over all right characters and  ` `                      ``suppose Kth char is same as ith  ` `                      ``character then choose minimum from  ` `                      ``current and two substring after  ` `                      ``ignoring ith and Kth char ` `                     ``*/` `                    ``for` `(``int` `K = i + ``2``; K <= j; K++) ` `                        ``if` `(str.charAt(i) == str.charAt(K)) ` `                            ``dp[i][j] = Math.min( ` `                                         ``dp[i + ``1``][K - ``1``] + ` `                                        ``dp[K + ``1``][j], dp[i][j]); ` `                ``} ` `            ``} ` `        ``} ` ` `  `        ``/* Uncomment below snippet to print actual dp tablex  ` `          `  `           ``for (int i = 0; i < N; i++){ ` `           ``System.out.println();  ` `           ``for (int j = 0; j < N; j++)  ` `           ``System.out.print(dp[i][j] + " "); ` `           ``} ` `            ``*/` `             `  `        ``return` `dp[``0``][N - ``1``]; ` `    ``} ` ` `  `    ``// Driver code to test above methods ` `    ``public` `static` `void` `main(String args[]) { ` `        ``String str = ``"2553432"``; ` `        ``System.out.println(minStepToDeleteString(str)); ` `    ``} ` `} ` `// This code is contributed by Sumit Ghosh `

## Python 3

 `# Python 3 program to find minimum ` `# step to delete a string ` ` `  `# method returns minimum step for  ` `# deleting the string, where in one  ` `# step a palindrome is removed  ` `def` `minStepToDeleteString(``str``): ` ` `  `    ``N ``=` `len``(``str``) ` ` `  `    ``# declare dp array and initialize  ` `    ``# it with 0s ` `    ``dp ``=` `[[``0` `for` `x ``in` `range``(N ``+` `1``)] ` `             ``for` `y ``in` `range``(N ``+` `1``)] ` ` `  `    ``# loop for substring length ` `    ``# we are considering ` `    ``for` `l ``in` `range``(``1``, N ``+` `1``): ` `         `  `        ``# loop with two variables i and j, denoting ` `        ``# starting and ending of substrings ` `        ``i ``=` `0` `        ``j ``=` `l ``-` `1` `        ``while` `j < N: ` `         `  `            ``# If substring length is 1,  ` `            ``# then 1 step will be needed ` `            ``if` `(l ``=``=` `1``): ` `                ``dp[i][j] ``=` `1` `            ``else``: ` `             `  `                ``# delete the ith char individually ` `                ``# and assign result for subproblem (i+1,j) ` `                ``dp[i][j] ``=` `1` `+` `dp[i ``+` `1``][j] ` ` `  `                ``# if current and next char are  ` `                ``# same, choose min from current  ` `                ``# and subproblem (i+2,j) ` `                ``if` `(``str``[i] ``=``=` `str``[i ``+` `1``]): ` `                    ``dp[i][j] ``=` `min``(``1` `+` `dp[i ``+` `2``][j], dp[i][j]) ` ` `  `                ``''' loop over all right characters and suppose ` `                    ``Kth char is same as ith character then ` `                    ``choose minimum from current and two ` `                    ``substring after ignoring ith and Kth char '''` `                ``for` `K ``in` `range``(i ``+` `2``, j ``+` `1``): ` `                    ``if` `(``str``[i] ``=``=` `str``[K]): ` `                        ``dp[i][j] ``=` `min``(dp[i ``+` `1``][K ``-` `1``] ``+`  `                                       ``dp[K ``+` `1``][j], dp[i][j]) ` `                         `  `            ``i ``+``=` `1` `            ``j ``+``=` `1` ` `  `    ``# Uncomment below snippet to print  ` `    ``# actual dp tablex  ` `    ``# for (int i = 0; i < N; i++, cout << endl) ` `    ``# for (int j = 0; j < N; j++) ` `    ``#     cout << dp[i][j] << " ";  ` ` `  `    ``return` `dp[``0``][N ``-` `1``] ` ` `  `# Driver Code ` `if` `__name__ ``=``=` `"__main__"``: ` `    ``str` `=` `"2553432"` `    ``print``( minStepToDeleteString(``str``)) ` ` `  `# This code is contributed by ChitraNayal `

## C#

 `// C# program to find minimum step to  ` `// delete a string ` `using` `System; ` ` `  `class` `GFG {     ` `     `  `    ``/* method returns minimum step for deleting ` `    ``the string, where in one step a ` `    ``palindrome is removed */` `    ``static` `int` `minStepToDeleteString(``string` `str) ` `    ``{ ` `        ``int` `N = str.Length; ` ` `  `        ``// declare dp array and initialize it  ` `        ``// with 0s ` `        ``int` `[,]dp = ``new` `int``[N + 1,N + 1]; ` `         `  `        ``for` `(``int` `i = 0; i <= N; i++) ` `            ``for` `(``int` `j = 0; j <= N; j++) ` `                ``dp[i,j] = 0; ` ` `  `        ``// loop for substring length we are ` `        ``// considering ` `        ``for` `(``int` `len = 1; len <= N; len++) { ` `             `  `            ``// loop with two variables i and j, ` `            ``// denoting starting and ending of  ` `            ``// substrings ` `            ``for` `(``int` `i = 0, j = len - 1; j < N; i++, j++) ` `            ``{ ` `     `  `                ``// If substring length is 1, then 1 ` `                ``// step will be needed ` `                ``if` `(len == 1) ` `                    ``dp[i,j] = 1; ` `                     `  `                ``else`  `                ``{ ` `                    ``// delete the ith char individually ` `                    ``// and assign result for  ` `                    ``// subproblem (i+1,j) ` `                    ``dp[i,j] = 1 + dp[i + 1,j]; ` ` `  `                    ``// if current and next char are same, ` `                    ``// choose min from current and  ` `                    ``// subproblem (i+2, j) ` `                    ``if` `(str[i] == str[i + 1]) ` `                        ``dp[i,j] = Math.Min(1 + dp[i + 2,j],  ` `                                                  ``dp[i,j]); ` ` `  `                    ``/* loop over all right characters and  ` `                    ``suppose Kth char is same as ith  ` `                    ``character then choose minimum from  ` `                    ``current and two substring after  ` `                    ``ignoring ith and Kth char ` `                    ``*/` `                    ``for` `(``int` `K = i + 2; K <= j; K++) ` `                        ``if` `(str[i] == str[K]) ` `                            ``dp[i,j] = Math.Min( ` `                                        ``dp[i + 1,K - 1] + ` `                                     ``dp[K + 1,j], dp[i,j]); ` `                ``} ` `            ``} ` `        ``} ` ` `  `        ``/* Uncomment below snippet to print actual dp tablex  ` `         `  `        ``for (int i = 0; i < N; i++){ ` `        ``System.out.println();  ` `        ``for (int j = 0; j < N; j++)  ` `        ``System.out.print(dp[i][j] + " "); ` `        ``} */` `             `  `        ``return` `dp[0,N - 1]; ` `    ``} ` ` `  `    ``// Driver code to test above methods ` `    ``public` `static` `void` `Main()  ` `    ``{ ` `        ``string` `str = ``"2553432"``; ` `        ``Console.Write(minStepToDeleteString(str)); ` `    ``} ` `} ` ` `  `// This code is contributed by nitin mittal `

Output:

```2
```