# 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:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:S = “acscbcca” K = 1Output:5Explanation: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 = 2Output: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**.

- Decrement the value of the
- 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)**.

- Increment the value of the
- 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:**

5

**Time Complexity:** O(N * log N)**Auxiliary Space:** O(1)