Maximize length of subsequence consisting of single distinct character possible by K increments in a string
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 operations 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()); // 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 Code int main() { string S = "acscbcca" ; int K = 1; maxSubsequenceLen(S, K); return 0; } |
Java
// Java program for the above approach import 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 operations static 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 code public 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 operations def 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 Code if __name__ = = '__main__' : S = "acscbcca" K = 1 maxSubsequenceLen(S, K) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to find the maximum length // of a subsequence of same characters // after at most K increment operations static 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 operations function 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 code var S = "acscbcca" ; var K = 1; maxSubsequenceLen(S, K); // This code is contributed by Amit Katiyar </script> |
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
Contact Us