C++ Greedy Approach String lexicographically largest subsequence














































C++ Greedy Approach String lexicographically largest subsequence



Lexicographically largest sub-sequence of the given string

Given a string str containing lowercase characters, the task is to find the lexicographically largest sub-sequence of str.

Examples:

Input: str = %u201Cabc%u201D
Output: c
All possible sub-sequences are %u201Ca%u201D, %u201Cab%u201D, %u201Cac%u201D, %u201Cb%u201D, %u201Cbc%u201D and %u201Cc%u201D
and %u201Cc%u201D is the largest among them (lexicographically)

Input: str = %u201Cgeeksforgeeks%u201D
Output: ss

Approach: Let mx be the lexicographically largest character in the string. Since we want the lexicographically largest sub-sequence we should include all occurrences of mx. Now after all the occurrences have been used, the same process can be repeated for the remaining string (i.e. sub-string after the last occurrence of mx) and so on until the there are no more characters left

Below is the implementation of the above approach:

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;

// Function to return the lexicographically
// largest sub-sequence of s
string getSubSeq(string s, int n)
{
    string res = "";
    int cr = 0;
    while (cr < n) {

        // Get the max character from the string
        char mx = s[cr];
        for (int i = cr + 1; i < n; i++)
            mx = max(mx, s[i]);
        int lst = cr;

        // Use all the occurrences of the
        // current maximum character
        for (int i = cr; i < n; i++)
            if (s[i] == mx) {
                res += s[i];
                lst = i;
            }

        // Repeat the steps for the remaining string
        cr = lst + 1;
    }
    return res;
}

// Driver code
int main()
{
    string s = "geeksforgeeks";
    int n = s.length();
    cout << getSubSeq(s, n);
}


Output:
ss

Time Complexity: O(N) where N is the length of the string.



More Articles of M Mounika:

Name Views Likes
C++ Segmented Sieve (Print Primes In a Range) 162 0
C++ Sieve Of Erastosthenes 135 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 285 0
C++ Find Non Repeating Elements in Array 87 0
C++ Merge Two Binary Trees 120 0
C++ Sum of Numbers From Root To Leaf Paths 89 0
C++ Meta Strings 91 0
C++ Flood Fill Algorithm 402 0
C++ smallest substring with maximum distinct characters 199 0
C++ Smallest window with all characters in string 93 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 69 0
C++ Number of Bracket Reversals needed to make expression Balanced 72 0
C++ String to Palindrome with Append Function 83 0
C++ WildCard pattern matching 76 0
C++ Anagram substring Search 72 0
C++ Manachars Algorithm 74 0
C++ Search String in Grid 83 0
C++ String Matching(Z Algorithm) 67 0
C++ String Matching(Naive Algorithm) 113 0
C++ String Matching(KMP Algorithm) 140 0
C++ Remove Duplicates From String 110 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 90 0
Disjoint Data Structures 93 1
C++ Segment Trees 321 2
C++ Trie Cost of Data 290 1
C++ Trie Datastructure 279 1
C++ Greedy Approach Minimum number of coins 526 0
C++ Greedy Approach Maximum height Pyramid 328 1
C++ Greedy Approach String lexicographically largest subsequence 247 0
C++ Greedy Approach Lexicographically largest subsequence 364 0
C++ Greedy Approach Prims MST 398 1
C++ Greedy Approach Krushkals MST 458 1
C++ Greedy Approach N-array maximum sum 333 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

Comments