# Minimum cost to make a string free of a subsequence

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 character 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 = ` `"geekcodergeeks"` `;` ` ` `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 = ` `"geekcodergeeks"` `;` ` ` `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` `=` `"geekcodergeeks"` ` ` `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 = ` `"geekcodergeeks"` `;` ` ` `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 = ` `"geekcodergeeks"` `;` `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>` |

**Output:**

2

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.