Given a string S consisting of N lowercase English alphabets, and an integer K and, an array cost[] of size 26 denoting the cost of each lowercase English alphabet, the task is to find the minimum cost to construct a subsequence of length K from the characters of the string S.
Examples:
Input: S = “aabcbc”, K = 3, cost[] = {2, 1, 3, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9}
Output: 4
Explanation:
One way to construct a string of size K(= 3) is:
Form the string “abb” taking two ‘b’s with a cost of (2*1 = 2), and one ‘a’ with a cost of (1*2 = 2).
Therefore, the total cost to construct the string “abb” is (2 + 2 = 4), which is the minimum possible.Input: S = “aaaca”, K = 1, cost[] = {2, 1, 3, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9}
Output: 2
Approach: The given problem can be solved by sorting the array cost[] in increasing order and include the first K characters having the minimum cost that are present in the given string S. Follow the steps below to solve the problem:
- Initialize a vector of pair of char and int say, V to store the character and the cost of that character.
- Also, initialize a map say mp with key as character and value as integers to store the frequency of each character of the string S.
- Traverse the given string using the variable i and in each iteration increment the value of mp[S[i]].
- Iterate over the range [0, 25] using the variable i and in each iteration append the pair {char(‘a’ + i), cost[i]} to the vector of pairs V.
- Sort the vector of pairs V[] according to the second element of the pair.
- Now, initialize a variable, say minCost as 0 to store the minimum cost of a subsequence of length K.
- Iterate over the range [0, 25] using the variable i and perform the following steps:
- Initialize a variable say, count as mp[‘a’ + i].
- If the value of count is less than K, then add the value of count*V[i].second to the value of minCost and update the value of K to K – count.
- Otherwise, add K*V[i].second to the value of minCost and break out of the loop.
- After completing the above steps, print the value of minCost as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Custom comparator to sort according// to the second elementbool comparator(pair<char, int> p1, pair<char, int> p2){ return p1.second < p2.second;}// Function to find the minimum cost// to construct a subsequence of the// length Kint minimumCost(string S, int N, int K, int cost[]){ // Stores the minimum cost int minCost = 0; // Stores the pair of character // and the cost of that character vector<pair<char, int> > V; // Stores the frequency of each // character unordered_map<char, int> mp; // Iterate in the range [0, N-1] for (int i = 0; i < N; i++) mp[S[i]]++; // Iterate in the range [0, 25] for (int i = 0; i < 26; i++) { V.push_back({ char('a' + i), cost[i] }); } // Sort the vector of pairs V // wrt the second element sort(V.begin(), V.end(), comparator); // Iterate in the range [0, 25] for (int i = 0; i < 26; i++) { // Stores the frequency of the // current char in the string int count = mp[char('a' + i)]; // If count is less than // or equal to K if (count >= K) { // Update the value of // minCost minCost += V[i].second * K; break; } else if (count < K) { // Update the value of // minCost minCost += V[i].second * count; // Update the value // of K K = K - count; } } // Print the value of minCost return minCost;}// Driver Codeint main(){ string S = "aabcbc"; int K = 3; int cost[26] = { 2, 1, 3, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 }; int N = S.length(); cout << minimumCost(S, N, K, cost); return 0;} |
Java
// Java program for the above approachimport java.util.*;public class Main { static class Pair { char first; int second; Pair(char first, int second) { this.first = first; this.second = second; } } // Custom comparator to sort according // to the second element public static Comparator<Pair> comparator = new Comparator<Pair>() { @Override public int compare(Pair p1, Pair p2) { return p1.second - p2.second; } }; public static int minimumCost(String S, int N, int K, int[] cost) { // Stores the minimum cost int minCost = 0; // Stores the pair of character // and the cost of that character List<Pair> V = new ArrayList<>(); // Stores the frequency of each // character Map<Character, Integer> mp = new HashMap<>(); // Iterate in the range [0, N-1] for (int i = 0; i < N; i++) { if (mp.containsKey(S.charAt(i))) { mp.put(S.charAt(i), mp.get(S.charAt(i)) + 1); } else { mp.put(S.charAt(i), 1); } } // Iterate in the range [0, 25] for (int i = 0; i < 26; i++) { if(mp.containsKey((char)('a' + i))){ V.add(new Pair((char)('a' + i), cost[i])); } } // Sort the list of pairs V // wrt the second element Collections.sort(V, comparator); // Iterate in the range [0, 25] for (Pair p : V) { // Stores the frequency of the // current char in the string int count = mp.get(p.first); // If count is less than // or equal to K if (count >= K) { // Update the value of // minCost minCost += p.second * K; break; } else if (count < K) { // Update the value of // minCost minCost += p.second * count; // Update the value // of K K = K - count; } } // Return the value of minCost return minCost; } // Driver Code public static void main(String[] args) { String S = "aabcbc"; int K = 3; int[] cost = { 2, 1, 3, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 }; int N = S.length(); System.out.println(minimumCost(S, N, K, cost)); } } |
Python3
# Python3 program for the above approach# Function to find the minimum cost# to construct a subsequence of the# length Kdef minimumCost(S, N, K, cost): # Stores the minimum cost minCost = 0 # Stores the pair of character # and the cost of that character V = [] # Stores the frequency of each # character mp = {} # Iterate in the range [0, N-1] for i in range(N): if (S[i] in mp): mp[S[i]] += 1 else: mp[S[i]] = 1 # Iterate in the range [0, 25] for i in range(26): V.append([chr(ord('a') + i), cost[i]]) # Sort the array of pairs V # with the second element while (1): flag = 0 for i in range(len(V) - 1): if (V[i][1] > V[i + 1][1]): temp = V[i] V[i] = V[i + 1] V[i + 1] = temp flag = 1 if (flag == 0): break # Iterate in the range [0, 25] for i in range(26): # Stores the frequency of the # current char in the string count = mp[chr(ord('a') + i)] # If count is less than # or equal to K if (count >= K): # Update the value of # minCost minCost += V[i][1] * K break elif (count < K): # Update the value of # minCost minCost += V[i][1] * count # Update the value # of K K = K - count # Print the value of minCost return minCost# Driver CodeS = "aabcbc"K = 3cost = [ 2, 1, 3, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 ]N = len(S)print(minimumCost(S, N, K, cost))# This code is contributed by _saurabh_jaiswal |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG { public class Pair { public char first; public int second; public Pair(char first, int second) { this.first = first; this.second = second; } } public static int minimumCost(string S, int N, int K, int[] cost) { // Stores the minimum cost int minCost = 0; // Stores the pair of character // and the cost of that character List<Pair> V = new List<Pair>(); // Stores the frequency of each // character Dictionary<char, int> mp = new Dictionary<char, int>(); // Iterate in the range [0, N-1] for (int i = 0; i < N; i++) { if (mp.ContainsKey(S[i])) { mp[S[i]] = mp[S[i]] + 1; } else { mp.Add(S[i], 1); } } // Iterate in the range [0, 25] for (int i = 0; i < 26; i++) { if (mp.ContainsKey((char)('a' + i))) { V.Add(new Pair((char)('a' + i), cost[i])); } } // Sort the list of pairs V // wrt the second element V.Sort((x, y) => x.second.CompareTo(y.second)); // Iterate in the range [0, 25] foreach(Pair p in V) { // Stores the frequency of the // current char in the string int count = mp[p.first]; // If count is less than // or equal to K if (count >= K) { // Update the value of // minCost minCost += p.second * K; break; } else if (count < K) { // Update the value of // minCost minCost += p.second * count; // Update the value // of K K = K - count; } } // Return the value of minCost return minCost; } // Driver code static void Main(string[] args) { string S = "aabcbc"; int K = 3; int[] cost = { 2, 1, 3, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 }; int N = S.Length; Console.WriteLine(minimumCost(S, N, K, cost)); }}// This code is contributed by ishankhandelwals. |
Javascript
<script>// Javascript program for the above approach// Function to find the minimum cost// to construct a subsequence of the// length Kfunction minimumCost(S, N, K, cost) { // Stores the minimum cost let minCost = 0; // Stores the pair of character // and the cost of that character let V = []; // Stores the frequency of each // character let mp = new Map(); // Iterate in the range [0, N-1] for (let i = 0; i < N; i++) { if (mp.has(S[i])) { mp.set(S[i], mp.get(S[i]) + 1) } else { mp.set(S[i], 1) } } // Iterate in the range [0, 25] for (let i = 0; i < 26; i++) { V.push([String.fromCharCode('a'.charCodeAt(0) + i), cost[i]]); } // Sort the array of pairs V // with the second element while (1) { let flag = 0; for (let i = 0; i < V.length - 1; i++) { if (V[i][1] > V[i + 1][1]) { let temp = V[i]; V[i] = V[i + 1]; V[i + 1] = temp; flag = 1 } } if(flag == 0){ break } } // Iterate in the range [0, 25] for (let i = 0; i < 26; i++) { // Stores the frequency of the // current char in the string let count = mp.get(String.fromCharCode('a'.charCodeAt(0) + i)); // If count is less than // or equal to K if (count >= K) { // Update the value of // minCost minCost += V[i][1] * K; break; } else if (count < K) { // Update the value of // minCost minCost += V[i][1] * count; // Update the value // of K K = K - count; } } // Print the value of minCost return minCost;}// Driver Codelet S = "aabcbc";let K = 3;let cost = [2, 1, 3, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9];let N = S.length;document.write(minimumCost(S, N, K, cost));// This code is contributed by gfgking.</script> |
Output
4
Time Complexity: O(N)
Auxiliary Space: O(1)
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!