Lexicographically smallest string formed by removing duplicates
Given a string S consisting of lowercase alphabets, the task is to find the lexicographically smallest string that can be obtained by removing duplicates from the given string S.
Examples:
Input: S = “yzxyz”
Output: xyz
Explanation: Removing the duplicate characters at indices 0 and 1 in the given string, the remaining string “xyz” consists only of unique alphabets only and is the smallest possible string in lexicographical order.Input: S = “acbc”
Output: “abc”
Explanation: Removing the duplicate characters at index 3 in the given string, the remaining string “abc” consists only of unique alphabets only and is the smallest possible string in lexicographical order.
Approach: Follow the steps below to solve the problem:
- Initialize a string res to store the resultant string.
- Store the frequency of each character present in the given string in an array freq[].
- Maintain an array vis[] for marking the characters that are already present in the resultant string res.
- Traverse the given string S and for each character S[i], perform the following:
- Decrease the frequency of the current character by 1.
- If the current character is not marked visited in the array vis[], then perform the following:
- If the last letter of res is less than S[i], add S[i] to res.
- If the last letter of res is greater than S[i] and the count of the last letter of res exceeds 0, then remove that character and mark visit[last letter of res] as 0 and continue this step till the above condition is satisfied.
- After breaking out from the above condition, add S[i] to res and mark visit[S[i]] as 1.
- After completing the above steps, print the string res as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function that finds lexicographically // smallest string after removing the // duplicates from the given string string removeDuplicateLetters(string s) { // Stores the frequency of characters int cnt[26] = { 0 }; // Mark visited characters int vis[26] = { 0 }; int n = s.size(); // Stores count of each character for ( int i = 0; i < n; i++) cnt[s[i] - 'a' ]++; // Stores the resultant string string res = "" ; for ( int i = 0; i < n; i++) { // Decrease the count of // current character cnt[s[i] - 'a' ]--; // If character is not already // in answer if (!vis[s[i] - 'a' ]) { // Last character > S[i] // and its count > 0 while (res.size() > 0 && res.back() > s[i] && cnt[res.back() - 'a' ] > 0) { // Mark letter unvisited vis[res.back() - 'a' ] = 0; res.pop_back(); } // Add s[i] in res and // mark it visited res += s[i]; vis[s[i] - 'a' ] = 1; } } // Return the resultant string return res; } // Driver Code int main() { // Given string S string S = "acbc" ; // Function Call cout << removeDuplicateLetters(S); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG{ // Function that finds lexicographically // smallest string after removing the // duplicates from the given string static String removeDuplicateLetters(String s) { // Stores the frequency of characters int [] cnt = new int [ 26 ]; // Mark visited characters int [] vis = new int [ 26 ]; int n = s.length(); // Stores count of each character for ( int i = 0 ; i < n; i++) cnt[s.charAt(i) - 'a' ]++; // Stores the resultant string String res = "" ; for ( int i = 0 ; i < n; i++) { // Decrease the count of // current character cnt[s.charAt(i) - 'a' ]--; // If character is not already // in answer if (vis[s.charAt(i) - 'a' ] == 0 ) { // Last character > S[i] // and its count > 0 int size = res.length(); while (size > 0 && res.charAt(size - 1 ) > s.charAt(i) && cnt[res.charAt(size - 1 ) - 'a' ] > 0 ) { // Mark letter unvisited vis[res.charAt(size - 1 ) - 'a' ] = 0 ; res = res.substring( 0 , size - 1 ); size--; } // Add s[i] in res and // mark it visited res += s.charAt(i); vis[s.charAt(i) - 'a' ] = 1 ; } } // Return the resultant string return res; } // Driver Code public static void main(String[] args) { // Given string S String S = "acbc" ; // Function Call System.out.println(removeDuplicateLetters(S)); } } // This code is contributed by akhilsaini |
Python3
# Python3 program for the above approach # Function that finds lexicographically # smallest after removing the # duplicates from the given string def removeDuplicateLetters(s): # Stores the frequency of characters cnt = [ 0 ] * 26 # Mark visited characters vis = [ 0 ] * 26 n = len (s) # Stores count of each character for i in s: cnt[ ord (i) - ord ( 'a' )] + = 1 # Stores the resultant string res = [] for i in range (n): # Decrease the count of # current character cnt[ ord (s[i]) - ord ( 'a' )] - = 1 # If character is not already # in answer if ( not vis[ ord (s[i]) - ord ( 'a' )]): # Last character > S[i] # and its count > 0 while ( len (res) > 0 and res[ - 1 ] > s[i] and cnt[ ord (res[ - 1 ]) - ord ( 'a' )] > 0 ): # Mark letter unvisited vis[ ord (res[ - 1 ]) - ord ( 'a' )] = 0 del res[ - 1 ] # Add s[i] in res and # mark it visited res + = s[i] vis[ ord (s[i]) - ord ( 'a' )] = 1 # Return the resultant string return "".join(res) # Driver Code if __name__ = = '__main__' : # Given S S = "acbc" # Function Call print (removeDuplicateLetters(S)) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; class GFG{ // Function that finds lexicographically // smallest string after removing the // duplicates from the given string static string removeDuplicateLetters( string s) { // Stores the frequency of characters int [] cnt = new int [26]; // Mark visited characters int [] vis = new int [26]; int n = s.Length; // Stores count of each character for ( int i = 0; i < n; i++) cnt[s[i] - 'a' ]++; // Stores the resultant string String res = "" ; for ( int i = 0; i < n; i++) { // Decrease the count of // current character cnt[s[i] - 'a' ]--; // If character is not already // in answer if (vis[s[i] - 'a' ] == 0) { // Last character > S[i] // and its count > 0 int size = res.Length; while (size > 0 && res[size - 1] > s[i] && cnt[res[size - 1] - 'a' ] > 0) { // Mark letter unvisited vis[res[size - 1] - 'a' ] = 0; res = res.Substring(0, size - 1); size--; } // Add s[i] in res and // mark it visited res += s[i]; vis[s[i] - 'a' ] = 1; } } // Return the resultant string return res; } // Driver Code public static void Main() { // Given string S string S = "acbc" ; // Function Call Console.WriteLine(removeDuplicateLetters(S)); } } // This code is contributed by akhilsaini |
Javascript
<script> // Javascript program for the above approach // Function that finds lexicographically // smallest string after removing the // duplicates from the given string function removeDuplicateLetters(s) { // Stores the frequency of characters var cnt = Array(26).fill(0); // Mark visited characters var vis = Array(26).fill( false ); var n = s.length; // Stores count of each character for ( var i = 0; i < n; i++) cnt[s[i].charCodeAt(0) - 'a' .charCodeAt(0)]++; // Stores the resultant string var res = "" ; for ( var i = 0; i < n; i++) { // Decrease the count of // current character cnt[s[i].charCodeAt(0) - 'a' .charCodeAt(0)]--; // If character is not already // in answer if (!vis[s[i].charCodeAt(0) - 'a' .charCodeAt(0)]) { // Last character > S[i] // and its count > 0 while (res.length > 0 && res[res.length-1].charCodeAt(0) > s[i].charCodeAt(0) && cnt[res[res.length-1].charCodeAt(0) - 'a' .charCodeAt(0)] > 0) { // Mark letter unvisited vis[res[res.length-1].charCodeAt(0) - 'a' .charCodeAt(0)] = 0; res = res.substring(0, res.length-1); } // Add s[i] in res and // mark it visited res += s[i]; vis[s[i].charCodeAt(0) - 'a' .charCodeAt(0)] = 1; } } // Return the resultant string return res; } // Driver Code // Given string S var S = "acbc" ; // Function Call document.write( removeDuplicateLetters(S)); </script> |
abc
Time Complexity: O(N)
Auxiliary Space: O(1), as we are using visited and cnt both array of fixed size 26