Given a string S of length N and a positive integer K, the task is to find the minimum total cost of picking K unique subsequence of the given string S such that the cost of picking a subsequence is the (length of S – length of that subsequence). If it is impossible to choose K unique subsequence, then print “-1“.
Examples:
Input: S = “efef”, K = 4
Output: 3
Explanation: There are 4 subsequences – “efef”, “efe”, “eef” and “fef”.
Hence, the total cost is 0 + 1 + 1 + 1 = 3.Input: S = “aaaaa”, K = 40
Output: -1
Naive Approach: The simplest approach is to generate all possible distinct subsequences of the given string S and choose K unique subsequence of maximum possible lengths. After choosing the K subsequences, the result will be (N*K – sum of lengths of all chosen K subsequences.)
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized by using Dynamic Programming. The idea is to initialize the 2D DP array such that dp[i[j] signifies the sum of lengths of a unique subsequence of length i ending at character j. Now, after precomputing choose those K lengths of subsequence whose sum of lengths is maximum. Follow the steps below to solve the problem:
- Initialize the variable ans as 0.
- Initialize a 2D array dp[N+1][128] with value 0.
- Iterate over the range [0, N) using the variable i and perform the following tasks:
- Iterate over the steps [i+1, 1) using the variable len and perform the following tasks:
- Set dp[len][s[i]] as accumulate(dp[len – 1].begin(), dp[len – 1].end(), 0L).
- Set dp[1][s[i]] as 1.
- Iterate over the steps [i+1, 1) using the variable len and perform the following tasks:
- Initialize a vector v[N+1] with values 0.
- Set v[0] as 1.
- Iterate over the range [1, N] using the variable i and perform the following tasks:
- Set v[i] as accumulate(dp[i].begin(), dp[i].end(), 0L).
- Reverse the vector v[].
- Iterate over a for loop using the variable i and perform the following tasks:
- Initialize a variable cantake as the minimum of k or v[i].
- Subtract the value cantake from k.
- Increase the value of ans by i*cantake.
- After performing the above steps, print the value of ans as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum cost to// find K unique subsequencesint minimumCost(string s, int k){ int N = s.length(), ans = 0; // Stores the dp states vector<vector<long long> > dp( N + 1, vector<long long>(128, 0)); // Precompute the dp states for (int i = 0; i < N; i++) { // Find the sum of length // of subsequence of length len // ending at index S[i] for (int len = i + 1; len > 1; len--) { dp[len][s[i]] = (accumulate(dp[len - 1].begin(), dp[len - 1].end(), 0L)); } // Sum of length of subsequence // of length 1 dp[1][s[i]] = 1; } vector<long long> v(N + 1, 0); v[0] = 1; for (int i = 1; i <= N; i++) { v[i] += accumulate(dp[i].begin(), dp[i].end(), 0L); } reverse(v.begin(), v.end()); for (int i = 0; i < v.size() and k > 0; i++) { long long cantake = min<long long>(k, v[i]); k -= cantake; ans += (i * cantake); } return k > 0 ? -1 : ans;}// Driver Codeint main(){ string S = "efef"; int K = 4; cout << minimumCost(S, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to find the minimum cost to // find K unique subsequences static int minimumCost(String s, int k) { int N = s.length(), ans = 0; // Stores the dp states int [][]dp = new int[N+1][128]; // Precompute the dp states for (int i = 0; i < N; i++) { // Find the sum of length // of subsequence of length len // ending at index S[i] for (int len = i + 1; len > 1; len--) { dp[len][s.charAt(i)] = (accumulate(dp[len - 1],0,dp[len - 1].length)); } // Sum of length of subsequence // of length 1 dp[1][s.charAt(i)] = 1; } int []v = new int[N + 1]; v[0] = 1; for (int i = 1; i <= N; i++) { v[i] += (accumulate(dp[i],0,dp[i].length)); } v = reverse(v); for (int i = 0; i < v.length && k > 0; i++) { long cantake = Math.min(k, v[i]); k -= cantake; ans += (i * cantake); } return k > 0 ? -1 : ans; } static int[] reverse(int a[]) { int i, n = a.length, t; for (i = 0; i < n / 2; i++) { t = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = t; } return a; } static int accumulate(int[] arr, int start, int end){ int sum=0; for(int i= 0; i < arr.length; i++) sum+=arr[i]; return sum; } // Driver Code public static void main(String[] args) { String S = "efef"; int K = 4; System.out.print(minimumCost(S, K)); }}// This code contributed by shikhasingrajput |
Python3
# python3 code for the above approachdef accumulate(a): total = 0 for i in a: total += i return total# Function to find the minimum cost to# find K unique subsequencesdef minimumCost(s, k): N, ans = len(s), 0 # Stores the dp states dp = [[0 for _ in range(128)] for _ in range(N + 1)] # Precompute the dp states for i in range(0, N): # Find the sum of length # of subsequence of length len # ending at index S[i] for le in range(i + 1, 1, -1): dp[le][ord(s[i])] = (accumulate(dp[le - 1])) # Sum of length of subsequence # of length 1 dp[1][ord(s[i])] = 1 v = [0 for _ in range(N + 1)] v[0] = 1 for i in range(1, N+1): v[i] += accumulate(dp[i]) v.reverse() for i in range(0, len(v), 1): if k <= 0: break cantake = min(k, v[i]) k -= cantake ans += (i * cantake) return -1 if k > 0 else ans# Driver Codeif __name__ == "__main__": S = "efef" K = 4 print(minimumCost(S, K)) # This code is contributed by rakeshsahni |
Javascript
<script> // JavaScript code for the above approach function accumulate(a) { let total = 0; for (let i in a) { total += a[i]; } return total; } // Function to find the minimum cost to // find K unique subsequences function minimumCost(s, k) { let N = s.length, ans = 0; // Stores the dp states let dp = new Array(N + 1) for (let i = 0; i < dp.length; i++) { dp[i] = new Array(128).fill(0); } // Precompute the dp states for (let i = 0; i < N; i++) { // Find the sum of length // of subsequence of length len // ending at index S[i] for (let len = i + 1; len > 1; len--) { dp[len][s[i]] = (accumulate(dp[len - 1])); } // Sum of length of subsequence // of length 1 dp[1][s[i]] = 1; } let v = new Array(N + 1).fill(0); v[0] = 1; for (let i = 1; i <= N; i++) { v[i] += accumulate(dp[i]) } v.reverse(); for (let i = 0; i < v.length && k > 0; i++) { let cantake = Math.min(k, v[i]); k -= cantake; ans += (i * cantake); } return k > 0 ? -1 : ans; } // Driver Code let S = "efef"; let K = 4; document.write(minimumCost(S, K)); // This code is contributed by Potta Lokesh</script> |
C#
// C# program for the above approachusing System;public class GFG{ public static int[] GetRow(int[,] matrix, int row) { var rowLength = matrix.GetLength(1); var rowVector = new int[rowLength]; for (var i = 0; i < rowLength; i++) rowVector[i] = matrix[row, i]; return rowVector; } // Function to find the minimum cost to // find K unique subsequences static int minimumCost(String s, int k) { int N = s.Length, ans = 0; // Stores the dp states int[,] dp = new int[N + 1,128]; // Precompute the dp states for (int i = 0; i < N; i++) { // Find the sum of length // of subsequence of length len // ending at index S[i] for (int len = i + 1; len > 1; len--) { int[] row = GetRow(dp,len-1); dp[len,s[i]] = (accumulate(row, 0, row.Length)); } // Sum of length of subsequence // of length 1 dp[1,s[i]] = 1; } int[] v = new int[N + 1]; v[0] = 1; for (int i = 1; i <= N; i++) { int[] row = GetRow(dp,i); v[i] += (accumulate(row, 0, row.Length)); } v = reverse(v); for (int i = 0; i < v.Length && k > 0; i++) { long cantake = Math.Min(k, v[i]); k -= (int)cantake; ans += (int)(i * cantake); } return k > 0 ? -1 : (int)ans; } static int[] reverse(int []a) { int i, n = a.Length, t; for (i = 0; i < n / 2; i++) { t = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = t; } return a; } static int accumulate(int[] arr, int start, int end) { int sum = 0; for (int i = 0; i < arr.Length; i++) sum += arr[i]; return sum; } // Driver Code public static void Main(String[] args) { String S = "efef"; int K = 4; Console.Write(minimumCost(S, K)); }}// This code is contributed by umadevi9616 |
Output
3
Time Complexity: O(N2)
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!