# Let see an example. Suppose S = "zzwzawa" and K = 2. Start with the largest character 'z'. Here fz = 3 >= K. So T will become "zzz" and we will remove letters from the left of S until all the z's are removed. So now S will became "awa". Next largest is 'y' but that occurs 0 times in k so we will skip it. We will skip 'w', 'v' etc also until we go to 'a' which occurs 2 times. Now T will become "zzzaa" and S will become a empty string. Our answer is "zzzaa".Below is implementation of this approach:// C++ program to find lexicographically largest // subsequence where every character appears at // least k times. #include <bits/stdc++.h> using namespace std; // Find lexicographically largest subsequence of // s[0..n-1] such that every character appears // at least k times. The result is filled in t[] void subsequence(char s[], char t[], int n, int k) {     int last = 0, cnt = 0, new_last = 0, size = 0;     // Starting from largest charter 'z' to 'a'     for (char ch = 'z'; ch >= 'a'; ch--) {         cnt = 0;         // Counting the frequency of the character         for (int i = last; i < n; i++) {             if (s[i] == ch)                 cnt++;         }         // If frequency is greater than k         if (cnt >= k) {             // From the last point we leave             for (int i = last; i < n; i++) {                 // check if string contain ch                 if (s[i] == ch) {                     // If yes, append to output string                     t[size++] = ch;                     new_last = i;                 }             }             // Update the last point.             last = new_last;         }     }     t[size] = '\0'; } // Driver code 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; } Output: nn

#### More Articles of M Mounika:

Name Views Likes
C++ Segmented Sieve (Print Primes In a Range) 163 0
C++ Sieve Of Erastosthenes 136 0
C++ Gold Mine Problem 295 0
C++ Merge K Sorted Arrays 117 0
C++ K Centers Problem 240 0
C++ Find Nth Catalan Number 311 0
C++ Inplace Rotate square matrix by 90 degrees 286 0
C++ Find Non Repeating Elements in Array 87 0
C++ Merge Two Binary Trees 121 0
C++ Sum of Numbers From Root To Leaf Paths 89 0
C++ Meta Strings 92 0
C++ Flood Fill Algorithm 402 0
C++ smallest substring with maximum distinct characters 200 0
C++ Smallest window with all characters in string 94 0
C++ Minimum Removal of Characters from string to make its permutation as palindrome 87 0
C++ Minimum characters added at front of string in palindrome conversion 70 0
C++ Number of Bracket Reversals needed to make expression Balanced 73 0
C++ String to Palindrome with Append Function 84 0
C++ WildCard pattern matching 76 0
C++ Anagram substring Search 72 0
C++ Manachars Algorithm 74 0
C++ Search String in Grid 84 0
C++ String Matching(Z Algorithm) 67 0
C++ String Matching(Naive Algorithm) 115 0
C++ String Matching(KMP Algorithm) 141 0
C++ Remove Duplicates From String 111 0
C++ Basics of String Manipulation 85 1
C++ Disjoint Data Structure Cycle Detection 87 0
C++ Problem On Disjoint Data Structures 95 0
C++ Disjoint Data Structures Part3 79 0
Disjoint Data Structures Part2 91 0
Disjoint Data Structures 93 1
C++ Segment Trees 321 2
C++ Trie Cost of Data 291 1
C++ Trie Datastructure 279 1
C++ Greedy Approach Minimum number of coins 526 0
C++ Greedy Approach Maximum height Pyramid 329 1
C++ Greedy Approach String lexicographically largest subsequence 247 0
C++ Greedy Approach Lexicographically largest subsequence 365 0
C++ Greedy Approach Prims MST 399 1
C++ Greedy Approach Krushkals MST 458 1
C++ Greedy Approach N-array maximum sum 334 1
C++ Greedy Approach Policemen Catch Thieves 563 1
C++ Greedy Approach Maximum product Subset 546 1
C++ Greedy Approach Minimum Product Subset 349 1
C++ Greedy Approach Fractional Knapsack 737 1
C++ Greedy Approach-Activity Selection Problem 745 1
C++ Greedy Approach-Egyptian Fractions 640 0
C++ Greedy Approach-Huffman Codes 1031 1
C++ Introduction to Greedy Approach 955 2