Given string str consisting of lowercase English alphabets and an array of positive integer arr[] both of the same length. The task is to remove some characters from the given string such that no sub-sequence in the string forms the string “code”. Cost of removing a character str[i] is arr[i]. Find the minimum cost to achieve the target.
Examples:
Input: str = “code”, arr[] = {3, 2, 1, 3}
Output: 1
Remove ‘d’ which costs the minimum.
Input: str = “ccooddde”, arr[] = {3, 2, 1, 3, 3, 5, 1, 6}
Output: 4
Remove both the ‘o’ which cost 1 + 3 = 4
Approach: If any sub-sequence with “code” is possible, then the removal of a single character is required. Cost for the removal of each character is given in arr[]. So, traverse the string and for each character which is either c, o, d or e calculate the cost of their removal. And finally, the minimum among the cost of removal of all characters is required minimum cost.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the minimum cost int findCost(string str, int arr[], int n) { long long costofC = 0, costofO = 0, costofD = 0, costofE = 0; // Traverse the string for ( int i = 0; i < n; i++) { // Min Cost to remove 'c' if (str[i] == 'c' ) costofC += arr[i]; // Min Cost to remove subsequence "co" else if (str[i] == 'o' ) costofO = min(costofC, costofO + arr[i]); // Min Cost to remove subsequence "cod" else if (str[i] == 'd' ) costofD = min(costofO, costofD + arr[i]); // Min Cost to remove subsequence "code" else if (str[i] == 'e' ) costofE = min(costofD, costofE + arr[i]); } // Return the minimum cost return costofE; } // Driver program int main() { string str = "geekcoderneveropen" ; int arr[] = { 1, 2, 1, 3, 4, 2, 6, 4, 6, 2, 3, 3, 3, 2 }; int n = sizeof (arr) / sizeof (arr[0]); cout << findCost(str, arr, n); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to return the minimum cost static int findCost(String str, int arr[], int n) { long costofC = 0 , costofO = 0 , costofD = 0 , costofE = 0 ; // Traverse the string for ( int i = 0 ; i < n; i++) { // Min Cost to remove 'c' if (str.charAt(i) == 'c' ) costofC += arr[i]; // Min Cost to remove subsequence "co" else if (str.charAt(i) == 'o' ) costofO = Math.min(costofC, costofO + arr[i]); // Min Cost to remove subsequence "cod" else if (str.charAt(i) == 'd' ) costofD = Math.min(costofO, costofD + arr[i]); // Min Cost to remove subsequence "code" else if (str.charAt(i) == 'e' ) costofE = Math.min(costofD, costofE + arr[i]); } // Return the minimum cost return ( int )costofE; } // Driver program public static void main(String[] args) { String str = "geekcoderneveropen" ; int arr[] = { 1 , 2 , 1 , 3 , 4 , 2 , 6 , 4 , 6 , 2 , 3 , 3 , 3 , 2 }; int n = arr.length; System.out.print(findCost(str, arr, n)); } } // This code has been contributed by 29AjayKumar |
Python3
# Python3 implementation of the approach # Function to return the minimum cost def findCost( str , arr, n): costofC, costofO = 0 , 0 costofD, costofE = 0 , 0 # Traverse the string for i in range (n): # Min Cost to remove 'c' if ( str [i] = = 'c' ): costofC + = arr[i] # Min Cost to remove subsequence "co" elif ( str [i] = = 'o' ): costofO = min (costofC, costofO + arr[i]) # Min Cost to remove subsequence "cod" elif ( str [i] = = 'd' ): costofD = min (costofO, costofD + arr[i]) # Min Cost to remove subsequence "code" elif ( str [i] = = 'e' ): costofE = min (costofD, costofE + arr[i]) # Return the minimum cost return costofE # Driver Code if __name__ = = '__main__' : str = "geekcoderneveropen" arr = [ 1 , 2 , 1 , 3 , 4 , 2 , 6 , 4 , 6 , 2 , 3 , 3 , 3 , 2 ] n = len (arr) print (findCost( str , arr, n)) # This code contributed by PrinciRaj1992 |
C#
// C# implementation of the approach using System; class GFG { // Function to return the minimum cost public static int findCost( string str, int [] arr, int n) { long costofC = 0, costofO = 0, costofD = 0, costofE = 0; // Traverse the string for ( int i = 0; i < n; i++) { // Min Cost to remove 'c' if (str[i] == 'c' ) { costofC += arr[i]; } // Min Cost to remove subsequence "co" else if (str[i] == 'o' ) { costofO = Math.Min(costofC, costofO + arr[i]); } // Min Cost to remove subsequence "cod" else if (str[i] == 'd' ) { costofD = Math.Min(costofO, costofD + arr[i]); } // Min Cost to remove subsequence "code" else if (str[i] == 'e' ) { costofE = Math.Min(costofD, costofE + arr[i]); } } // Return the minimum cost return ( int )costofE; } // Driver program public static void Main( string [] args) { string str = "geekcoderneveropen" ; int [] arr = new int [] {1, 2, 1, 3, 4, 2, 6, 4, 6, 2, 3, 3, 3, 2}; int n = arr.Length; Console.Write(findCost(str, arr, n)); } } // This code is contributed by shrikanth13 |
Javascript
<script> // Javascript implementation of the approach // Function to return the Math.minimum cost function findCost(str, arr, n) { var costofC = 0, costofO = 0, costofD = 0, costofE = 0; // Traverse the string for ( var i = 0; i < n; i++) { // Math.min Cost to remove 'c' if (str[i] == 'c' ) costofC += arr[i]; // Math.min Cost to remove subsequence "co" else if (str[i] == 'o' ) costofO = Math.min(costofC, costofO + arr[i]); // Math.min Cost to remove subsequence "cod" else if (str[i] == 'd' ) costofD = Math.min(costofO, costofD + arr[i]); // Math.min Cost to remove subsequence "code" else if (str[i] == 'e' ) costofE = Math.min(costofD, costofE + arr[i]); } // Return the Math.minimum cost return costofE; } // Driver program var str = "geekcoderneveropen" ; var arr = [ 1, 2, 1, 3, 4, 2, 6, 4, 6, 2, 3, 3, 3, 2 ]; var n = arr.length; document.write( findCost(str, arr, n)); </script> |
2
Time Complexity: O(n), where n is the size of the given array and string.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!