Lexicographically largest string possible consisting of at most K consecutive similar characters | C ++ program for the above approach ; Function to return nearest lower character ; Traverse charset from start - 1 ; If no character can be appended ; Function to find largest string ; Stores the frequency of characters ; Traverse the string ; Append larger character ; Decrease count in charset ; Increase count ; Check if count reached to charLimit ; Find nearest lower char ; If no character can be appended ; Append nearest lower character ; Reset count for next calculation ; Return new largest string ; Driver code ; Given string s
#include <bits/stdc++.h> NEW_LINE using namespace std ; char nextAvailableChar ( vector < int > charset , int start ) { for ( int i = start - 1 ; i >= 0 ; i -- ) { if ( charset [ i ] > 0 ) { charset [ i ] -- ; return char ( i + ' a ' ) ; } } return ' \0' ; } string newString ( string originalLabel , int limit ) { int n = originalLabel . length ( ) ; vector < int > charset ( 26 , 0 ) ; string newStrings = " " ; for ( char i : originalLabel ) charset [ i - ' a ' ] ++ ; for ( int i = 25 ; i >= 0 ; i -- ) { int count = 0 ; while ( charset [ i ] > 0 ) { newStrings += char ( i + ' a ' ) ; charset [ i ] -- ; count ++ ; if ( charset [ i ] > 0 && count == limit ) { char next = nextAvailableChar ( charset , i ) ; if ( next == ' \0' ) return newStrings ; newStrings += next ; count = 0 ; } } } return newStrings ; } int main ( ) { string S = " ccbbb " ; int K = 2 ; cout << ( newString ( S , K ) ) ; }