Given a string S consisting of lowercase characters and an integer K, the task is to find the maximum length of a subsequence consisting of a single distinct character possible by incrementing at most K characters.
Examples:
Input: S = “acscbcca” K = 1
Output: 5
Explanation: Incrementing the character S[4] from ‘b’ to ‘c’, modifies the string to “acscccca”. Therefore, longest subsequence of same characters is “ccccc”. Length of the subsequence is 5.Input: S = “adscassr”, K = 2
Output: 4
Approach: This given problem can be solved by using the Sliding window technique and Sorting. Follow the steps to solve this problem:
- Initialize the variables, say start, end, and sum to 0 that stores the starting and ending indexes of the subsequences the sum of the sliding window.
- Initialize a variable, say ans to INT_MIN that stores the length of the resultant longest subsequence.
- Sort the given string S.
- Traverse the string over the range [0, N – 1] and perform the following steps:
- Increment the value of the sum by the value (S[end] – ‘a’).
- Iterate a loop until the value of (sum + K) is less than (S[end] – ‘a’) * (end – start + 1) and perform the following steps:
- Decrement the value of the sum by (S[start] – ‘a’).
- Increment the value of the start by 1.
- After the above steps, all the characters over the range [start, end] can be made equal by using at most K increments. Therefore, update the value of ans as the maximum of ans and (end – start + 1).
- After completing the above steps, print the value of ans 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;// Function to find the maximum length// of a subsequence of same characters// after at most K increment operationsvoid maxSubsequenceLen(string S, int K){ // Store the size of S int N = S.length(); int start = 0, end = 0; // Sort the given string sort(S.begin(), S.end()); // Stores the maximum length and the // sum of the sliding window int ans = INT_MIN, sum = 0; // Traverse the string S for (end = 0; end < N; end++) { // Add the current character // to the window sum = sum + (S[end] - 'a'); // Decrease the window size while (sum + K < (S[end] - 'a') * (end - start + 1)) { // Update the value of sum sum = sum - (S[start] - 'a'); // Increment the value // of start start++; } // Update the maximum window size ans = max(ans, end - start + 1); } // Print the resultant maximum // length of the subsequence cout << ans;}// Driver Codeint main(){ string S = "acscbcca"; int K = 1; maxSubsequenceLen(S, K); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.math.*;import java.util.Arrays;class GFG{ // Function to find the maximum length// of a subsequence of same characters// after at most K increment operationsstatic void maxSubsequenceLen(String s, int K){ // Store the size of s int N = s.length(); int start = 0, end = 0; // Sort the given string //sort(S.begin(), S.end()); // convert input string to char array char S[] = s.toCharArray(); // sort tempArray Arrays.sort(S); // Stores the maximum length and the // sum of the sliding window int ans = Integer.MIN_VALUE, sum = 0; // Traverse the string S for(end = 0; end < N; end++) { // Add the current character // to the window sum = sum + (S[end] - 'a'); // Decrease the window size while (sum + K < (S[end] - 'a') * (end - start + 1)) { // Update the value of sum sum = sum - (S[start] - 'a'); // Increment the value // of start start++; } // Update the maximum window size ans = Math.max(ans, end - start + 1); } // Print the resultant maximum // length of the subsequence System.out.println(ans);}// Driver codepublic static void main(String args[]){ String S = "acscbcca"; int K = 1; maxSubsequenceLen(S, K);}}// This code is contributed by jana_sayantan |
Python3
# Python3 program for the above approach# Function to find the maximum length# of a subsequence of same characters# after at most K increment operationsdef maxSubsequenceLen(S, K): # Store the size of S N = len(S) start, end = 0, 0 # Sort the given string S = sorted(S) # Stores the maximum length and the # sum of the sliding window ans, sum =-10**9, 0 # Traverse the S for end in range(N): # Add the current character # to the window sum = sum + (ord(S[end]) - ord('a')) # Decrease the window size while (sum + K < (ord(S[end]) - ord('a')) * (end - start + 1)): # Update the value of sum sum = sum - (ord(S[start]) - ord('a')) # Increment the value # of start start += 1 # Update the maximum window size ans = max(ans, end - start + 1) # Print the resultant maximum # length of the subsequence print (ans)# Driver Codeif __name__ == '__main__': S = "acscbcca" K = 1 maxSubsequenceLen(S, K)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG {// Function to find the maximum length// of a subsequence of same characters// after at most K increment operationsstatic void maxSubsequenceLen(string s, int K){ // Store the size of s int N = s.Length; int start = 0, end = 0; // Sort the given string //sort(S.begin(), S.end()); // convert input string to char array char[] S= s.ToCharArray(); // sort tempArray Array.Sort(S); // Stores the maximum length and the // sum of the sliding window int ans = Int32.MinValue, sum = 0; // Traverse the string S for(end = 0; end < N; end++) { // Add the current character // to the window sum = sum + (S[end] - 'a'); // Decrease the window size while (sum + K < (S[end] - 'a') * (end - start + 1)) { // Update the value of sum sum = sum - (S[start] - 'a'); // Increment the value // of start start++; } // Update the maximum window size ans = Math.Max(ans, end - start + 1); } // Print the resultant maximum // length of the subsequence Console.WriteLine(ans);} // Driver Code public static void Main() { string S = "acscbcca"; int K = 1; maxSubsequenceLen(S, K); }}// This code is contributed by souravghosh0416. |
Javascript
<script>// Javascript program for the above approach// Function to find the maximum length// of a subsequence of same characters// after at most K increment operationsfunction maxSubsequenceLen(s, K){ // Store the size of s var N = s.length; var start = 0, end = 0; // Sort the given string //sort(S.begin(), S.end()); // convert input string to char array var S = s.split(''); // sort tempArray S.sort(); // Stores the maximum length and the // sum of the sliding window var ans = Number.MIN_VALUE, sum = 0; // Traverse the string S for(end = 0; end < N; end++) { // Add the current character // to the window sum = sum + (S[end].charCodeAt(0) - 'a'.charCodeAt(0)); // Decrease the window size while (sum + K < (S[end].charCodeAt(0) - 'a'.charCodeAt(0)) * (end - start + 1)) { // Update the value of sum sum = sum - (S[start].charCodeAt(0) - 'a'.charCodeAt(0)); // Increment the value // of start start++; } // Update the maximum window size ans = Math.max(ans, end - start + 1); } // Print the resultant maximum // length of the subsequence document.write(ans);}// Driver codevar S = "acscbcca";var K = 1;maxSubsequenceLen(S, K);// This code is contributed by Amit Katiyar </script> |
Output:
5
Time Complexity: O(N * log N), only one traversal of string takes O(n) time and sorting them takes extra log N time and thus the overall time complexity turns out to be O( N log N)
Auxiliary Space: O(1), since no extra array is used so it has constant space
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!
