Lexicographically largest subsequence containing all distinct characters only once
Given a string S, the task is to find the lexicographically largest subsequence that can be formed using all distinct characters only once from the given string.
Examples:
Input: S = ababc
Output: bac
Explanation:
All possible subsequences containing all the characters in S exactly once are {“abc”, “bac”}. The lexicographically maximum among all the subsequences is “bac”.Input: S = “zydsbacab”
Output: zydscab
Approach: The given problem can be solved using Stack. The idea is to traverse the string and store those characters in the stack in lexicographically largest order so as to generate the resultant string. Follow the steps below to solve the given problem:
- Store the frequency of all the characters of the string S in an array, say count[].
- Initialize an array, say visited[], that stores whether any character is present in the stack or not.
- Traverse the given string S using the variable i and perform the following steps:
- Decrement the frequency of character S[i] in the array count[] by 1.
- Now, if the character is already present in the stack, then continue to the next iteration.
- Otherwise, check if the current character is greater than the top character in the stack and the frequency of the top character is greater than 0, then keep popping out the top element from the stack.
- After the above steps, add the current character and mark it as visited in the array visited[].
- After completing the above steps, generate the string using the characters in the stack and print the reverse of it to get the lexicographically largest subsequence.
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 lexicographically // largest subsequence consisting of all // distinct characters of S only once string lexicoMaxSubsequence(string s, int n) { stack< char > st; // Stores if any alphabet is present // in the current stack vector< int > visited(26, 0), cnt(26, 0); // Findthe number of occurrences of // the character s[i] for ( int i = 0; i < n; i++) { cnt[s[i] - 'a' ]++; } for ( int i = 0; i < n; i++) { // Decrease the character count // in remaining string cnt[s[i] - 'a' ]--; // If character is already present // in the stack if (visited[s[i] - 'a' ]) { continue ; } // if current character is greater // than last character in stack // then pop the top character while (!st.empty() && st.top() < s[i] && cnt[st.top() - 'a' ] != 0) { visited[st.top() - 'a' ] = 0; st.pop(); } // Push the current character st.push(s[i]); visited[s[i] - 'a' ] = 1; } // Stores the resultant string string s1; // Generate the string while (!st.empty()) { s1 = st.top() + s1; st.pop(); } // Return the resultant string return s1; } // Driver Code int main() { string S = "ababc" ; int N = S.length(); cout << lexicoMaxSubsequence(S, N); return 0; } |
Java
/*package whatever //do not write package name here */ import java.io.*; import java.util.*; class GFG { // Function to find the lexicographically // largest subsequence consisting of all // distinct characters of S only once static String lexicoMaxSubsequence(String s, int n) { Stack<Character> st = new Stack<Character>(); // Stores if any alphabet is present // in the current stack int [] visited = new int [ 26 ]; int [] cnt = new int [ 26 ]; for ( int i = 0 ; i < 26 ; i++) { visited[i] = 0 ; cnt[i] = 0 ; } // Findthe number of occurrences of // the character s[i] for ( int i = 0 ; i < n; i++) { cnt[s.charAt(i) - 'a' ]++; } for ( int i = 0 ; i < n; i++) { // Decrease the character count // in remaining string cnt[s.charAt(i) - 'a' ]--; // If character is already present // in the stack if (visited[s.charAt(i) - 'a' ] > 0 ) { continue ; } // if current character is greater // than last character in stack // then pop the top character while (!st.empty() && st.peek() < s.charAt(i) && cnt[st.peek() - 'a' ] != 0 ) { visited[st.peek() - 'a' ] = 0 ; st.pop(); } // Push the current character st.push(s.charAt(i)); visited[s.charAt(i) - 'a' ] = 1 ; } // Stores the resultant string String s1 = "" ; // Generate the string while (!st.empty()) { s1 = st.peek() + s1; st.pop(); } // Return the resultant string return s1; } // Driver Code public static void main(String[] args) { String S = "ababc" ; int N = S.length(); System.out.println(lexicoMaxSubsequence(S, N)); } } // This code is contributed by maddler. |
Python3
# Python3 program for the above approach # Function to find the lexicographically # largest subsequence consisting of all # distinct characters of S only once def lexicoMaxSubsequence(s, n): st = [] # Stores if any alphabet is present # in the current stack visited = [ 0 ] * ( 26 ) cnt = [ 0 ] * ( 26 ) for i in range ( 26 ): visited[i] = 0 cnt[i] = 0 # Findthe number of occurrences of # the character s[i] for i in range (n): cnt[ ord (s[i]) - ord ( 'a' )] + = 1 for i in range (n): # Decrease the character count # in remaining string cnt[ ord (s[i]) - ord ( 'a' )] - = 1 # If character is already present # in the stack if (visited[ ord (s[i]) - ord ( 'a' )] > 0 ): continue # if current character is greater # than last character in stack # then pop the top character while ( len (st) > 0 and ord (st[ - 1 ]) < ord (s[i]) and cnt[ ord (st[ - 1 ]) - ord ( 'a' )] ! = 0 ): visited[ ord (st[ - 1 ]) - ord ( 'a' )] = 0 st.pop() # Push the current character st.append(s[i]) visited[ ord (s[i]) - ord ( 'a' )] = 1 # Stores the resultant string s1 = "" # Generate the string while ( len (st) > 0 ): s1 = st[ - 1 ] + s1 st.pop() # Return the resultant string return s1 S = "ababc" N = len (S) print (lexicoMaxSubsequence(S, N)) # This code is contributed by decode2207. |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to find the lexicographically // largest subsequence consisting of all // distinct characters of S only once static string lexicoMaxSubsequence( string s, int n) { Stack< char > st = new Stack< char >(); // Stores if any alphabet is present // in the current stack int [] visited = new int [26]; int [] cnt = new int [26]; for ( int i = 0; i < 26; i++) { visited[i] = 0; cnt[i] = 0; } // Findthe number of occurrences of // the character s[i] for ( int i = 0; i < n; i++) { cnt[s[i] - 'a' ]++; } for ( int i = 0; i < n; i++) { // Decrease the character count // in remaining string cnt[s[i] - 'a' ]--; // If character is already present // in the stack if (visited[s[i] - 'a' ] > 0) { continue ; } // if current character is greater // than last character in stack // then pop the top character while (st.Count > 0 && st.Peek() < s[i] && cnt[st.Peek() - 'a' ] != 0) { visited[st.Peek() - 'a' ] = 0; st.Pop(); } // Push the current character st.Push(s[i]); visited[s[i] - 'a' ] = 1; } // Stores the resultant string string s1 = "" ; // Generate the string while (st.Count > 0) { s1 = st.Peek() + s1; st.Pop(); } // Return the resultant string return s1; } static void Main() { string S = "ababc" ; int N = S.Length; Console.Write(lexicoMaxSubsequence(S, N)); } } // This code is contributed by suresh07. |
Javascript
<script> // Javascript program for the above approach // Function to find the lexicographically // largest subsequence consisting of all // distinct characters of S only once function lexicoMaxSubsequence(s, n) { let st = []; // Stores if any alphabet is present // in the current stack let visited = new Array(26); let cnt = new Array(26); for (let i = 0; i < 26; i++) { visited[i] = 0; cnt[i] = 0; } // Findthe number of occurrences of // the character s[i] for (let i = 0; i < n; i++) { cnt[s[i].charCodeAt() - 'a' .charCodeAt()]++; } for (let i = 0; i < n; i++) { // Decrease the character count // in remaining string cnt[s[i].charCodeAt() - 'a' .charCodeAt()]--; // If character is already present // in the stack if (visited[s[i].charCodeAt() - 'a' .charCodeAt()] > 0) { continue ; } // if current character is greater // than last character in stack // then pop the top character while (st.length > 0 && st[st.length - 1].charCodeAt() < s[i].charCodeAt() && cnt[st[st.length - 1].charCodeAt() - 'a' .charCodeAt()] != 0) { visited[st[st.length - 1].charCodeAt() - 'a' .charCodeAt()] = 0; st.pop(); } // Push the current character st.push(s[i]); visited[s[i].charCodeAt() - 'a' .charCodeAt()] = 1; } // Stores the resultant string let s1 = "" ; // Generate the string while (st.length > 0) { s1 = st[st.length - 1] + s1; st.pop(); } // Return the resultant string return s1; } let S = "ababc" ; let N = S.length; document.write(lexicoMaxSubsequence(S, N)); // This code is contributed by divyeshrabadiya07. </script> |
bac
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us