Tutorialspoint.dev

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++



//  C++ program to find minimum step to delete a string
#include <bits/stdc++.h>
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[0][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

PHP


Output:

2

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter