Maximize length of subsequence consisting of single distinct character possible by K increments in a string

0 0 6 minutes read

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>

Output:

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

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!