Given string str. You are allowed to delete only some contiguous characters if all the characters are the same in a single operation. The task is to find the minimum number of operations required to completely delete the string.
Examples:
Input: str = “abcddcba”
Output: 4
Delete dd, then the string is “abccba”
Delete cc, then the string is “abba”
Delete bb, then the string is “aa”
Delete aa, then the string is null.
Input: str = “abc”
Output: 3
Approach: The problem can be solved using <a href=”http://wwl<=iDynamic Programming and Divide and Conquer technique.
Let dp[l][r] be the answer for sub-string s[l, l+1, l+2, …r]. Then we have two cases:
- The first letter of the sub-string is deleted separately from the rest, then dp[l][r] = 1 + dp[l+1][r].
- The first letter of the sub-string is deleted alongside with some other letter (both letters must be equal), then dp[l][r] = dp[l+1][i-1] + dp[i][r], given that l ? i ? r and s[i] = s[l].
The following two cases can be recursively called along with memoization to avoid repetitive function calls.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;const int N = 10;// Function to return the minimum number of// delete operationsint findMinimumDeletion(int l, int r, int dp[N][N], string s){ if (l > r) return 0; if (l == r) return 1; if (dp[l][r] != -1) return dp[l][r]; // When a single character is deleted int res = 1 + findMinimumDeletion(l + 1, r, dp, s); // When a group of consecutive characters // are deleted if any of them matches for (int i = l + 1; i <= r; ++i) { // When both the characters are same then // delete the letters in between them if (s[l] == s[i]) res = min(res, findMinimumDeletion(l + 1, i - 1, dp, s) + findMinimumDeletion(i, r, dp, s)); } // Memoize return dp[l][r] = res;}// Driver codeint main(){ string s = "abcddcba"; int n = s.length(); int dp[N][N]; memset(dp, -1, sizeof dp); cout << findMinimumDeletion(0, n - 1, dp, s); return 0;} |
Java
// Java implementation of the approachclass GFG{ static int N = 10; // Function to return the minimum number of // delete operations static int findMinimumDeletion(int l, int r, int dp[][], String s) { if (l > r) { return 0; } if (l == r) { return 1; } if (dp[l][r] != -1) { return dp[l][r]; } // When a single character is deleted int res = 1 + findMinimumDeletion(l + 1, r, dp, s); // When a group of consecutive characters // are deleted if any of them matches for (int i = l + 1; i <= r; ++i) { // When both the characters are same then // delete the letters in between them if (s.charAt(l) == s.charAt(i)) { res = Math.min(res, findMinimumDeletion(l + 1, i - 1, dp, s) + findMinimumDeletion(i, r, dp, s)); } } // Memoize return dp[l][r] = res; } // Driver code public static void main(String[] args) { String s = "abcddcba"; int n = s.length(); int dp[][] = new int[N][N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { dp[i][j] = -1; } } System.out.println(findMinimumDeletion(0, n - 1, dp, s)); }}// This code contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach# Function to return the minimum# number of delete operationsdef findMinimumDeletion(l, r, dp, s): if l > r: return 0 if l == r: return 1 if dp[l][r] != -1: return dp[l][r] # When a single character is deleted res = 1 + findMinimumDeletion(l + 1, r, dp, s) # When a group of consecutive characters # are deleted if any of them matches for i in range(l + 1, r + 1): # When both the characters are same then # delete the letters in between them if s[l] == s[i]: res = min(res, findMinimumDeletion(l + 1, i - 1, dp, s) + findMinimumDeletion(i, r, dp, s)) # Memoize dp[l][r] = res return res# Driver codeif __name__ == "__main__": s = "abcddcba" n = len(s) N = 10 dp = [[-1 for i in range(N)] for j in range(N)] print(findMinimumDeletion(0, n - 1, dp, s))# This code is contributed by Rituraj Jain |
C#
// C# implementation of the approachusing System;class GFG{ static int N = 10; // Function to return the minimum number of // delete operations static int findMinimumDeletion(int l, int r, int [,]dp, String s) { if (l > r) { return 0; } if (l == r) { return 1; } if (dp[l, r] != -1) { return dp[l, r]; } // When a single character is deleted int res = 1 + findMinimumDeletion(l + 1, r, dp, s); // When a group of consecutive characters // are deleted if any of them matches for (int i = l + 1; i <= r; ++i) { // When both the characters are same then // delete the letters in between them if (s[l] == s[i]) { res = Math.Min(res, findMinimumDeletion(l + 1, i - 1, dp, s) + findMinimumDeletion(i, r, dp, s)); } } // Memoize return dp[l,r] = res; } // Driver code public static void Main(String[] args) { String s = "abcddcba"; int n = s.Length; int [,]dp = new int[N, N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { dp[i, j] = -1; } } Console.WriteLine(findMinimumDeletion(0, n - 1, dp, s)); }}// This code has been contributed by 29AjayKumar |
Javascript
<script>// JavaScript implementation of the approachvar N = 10;// Function to return the minimum number of// delete operationsfunction findMinimumDeletion(l, r, dp, s){ if (l > r) return 0; if (l == r) return 1; if (dp[l][r] != -1) return dp[l][r]; // When a single character is deleted var res = 1 + findMinimumDeletion(l + 1, r, dp, s); // When a group of consecutive characters // are deleted if any of them matches for (var i = l + 1; i <= r; ++i) { // When both the characters are same then // delete the letters in between them if (s[l] == s[i]) res = Math.min(res, findMinimumDeletion(l + 1, i - 1, dp, s) + findMinimumDeletion(i, r, dp, s)); } // Memoize return dp[l][r] = res;}// Driver codevar s = "abcddcba";var n = s.length;var dp = Array.from(Array(N), ()=> Array(N).fill(-1));document.write( findMinimumDeletion(0, n - 1, dp, s));</script> |
PHP
<?php// PHP implementation of the approach$GLOBALS['N'] = 10;// Function to return the minimum // number of delete operationsfunction findMinimumDeletion($l, $r, $dp, $s){ if ($l > $r) return 0; if ($l == $r) return 1; if ($dp[$l][$r] != -1) return $dp[$l][$r]; // When a single character is deleted $res = 1 + findMinimumDeletion($l + 1, $r, $dp, $s); // When a group of consecutive characters // are deleted if any of them matches for ($i = $l + 1; $i <= $r; ++$i) { // When both the characters are same then // delete the letters in between them if ($s[$l] == $s[$i]) $res = min($res, findMinimumDeletion($l + 1, $i - 1, $dp, $s) + findMinimumDeletion($i, $r, $dp, $s)); } // Memoize return $dp[$l][$r] = $res;}// Driver code$s = "abcddcba";$n = strlen($s);$dp = array(array());for($i = 0; $i < $GLOBALS['N']; $i++) for($j = 0; $j < $GLOBALS['N']; $j++) $dp[$i][$j] = -1 ; echo findMinimumDeletion(0, $n - 1, $dp, $s);// This code is contributed by Ryuga?> |
Output
4
Time Complexity: O(N*N*N), as we have O(N*N) states in dp table and in each state we are traversing a loop with complexity O(N). Where N is the length of the string.
Auxiliary Space: O(N*N), as we are using extra space for the dp matrix. Where N is the length of the string.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
