Lexicographically largest subsequence such that every character occurs at least k times | C ++ program to find lexicographically largest subsequence where every character appears at least k times . ; Find lexicographically largest subsequence of s [ 0. . n - 1 ] such that every character appears at least k times . The result is filled in t [ ] ; Starting from largest charter ' z ' to ' a ' ; Counting the frequency of the character ; If frequency is greater than k ; From the last point we leave ; check if string contain ch ; If yes , append to output string ; Update the last point . ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void subsequence ( char s [ ] , char t [ ] , int n , int k ) { int last = 0 , cnt = 0 , new_last = 0 , size = 0 ; for ( char ch = ' z ' ; ch >= ' a ' ; ch -- ) { cnt = 0 ; for ( int i = last ; i < n ; i ++ ) { if ( s [ i ] == ch ) cnt ++ ; } if ( cnt >= k ) { for ( int i = last ; i < n ; i ++ ) { if ( s [ i ] == ch ) { t [ size ++ ] = ch ; new_last = i ; } } last = new_last ; } } t [ size ] = ' \0' ; } int main ( ) { char s [ ] = " banana " ; int n = sizeof ( s ) ; int k = 2 ; char t [ n ] ; subsequence ( s , t , n - 1 , k ) ; cout << t << endl ; return 0 ; }