26- Remove Duplicate Letters

The problem can be found at the following link: Question Link

My Approach

1. Initialize two vectors:

   • freq: A vector of size 26 to keep track of the frequency of each lowercase letter in the input string s. Initialize all elements to 0.

   • visited: A vector of size 26 to keep track of whether a character has been visited or not. Initialize all elements to 0.

2. Iterate through the characters of the input string s:

   • For each character ch in s, increment the corresponding frequency in the freq vector. This will count how many times each character appears in the string.

3. Initialize an empty string ans to store the result.

4. Get the length of the input string s and store it in a variable n.

5. Iterate through the characters of the input string s again using a loop from i=0 to i<n:

   • Decrement the frequency of the current character s[i] in the freq vector.

6. Check if the current character s[i] has not been visited yet (i.e., visited[s[i]-'a'] is 0):

   • Enter a while loop that continues as long as the following conditions are met:

     • ans is not empty (ans.size() is non-zero).

     • The last character in ans (i.e., ans.back()) is greater than the current character s[i].

     • The frequency of the last character in ans is greater than 0 (i.e., freq[ans.back()-'a'] > 0).

   • Inside the while loop:

     • Mark the character as not visited by setting visited[ans.back()-'a'] to 0.

     • Remove the last character from ans by using ans.pop_back().

7. After exiting the while loop, append the current character s[i] to the ans string to add it to the result.

8. Mark the current character s[i] as visited by setting visited[s[i]-'a'] to 1.

9. Repeat steps 5-8 for all characters in the input string s.

10. Return the final ans string, which contains the unique characters from the input string in lexicographically smallest order while maintaining their relative order.

Time and Auxiliary Space Complexity

• Time Complexity: O(n)

• Auxiliary Space Complexity: O(n)

Code (C++)

class Solution {
public:
    string removeDuplicateLetters(string s) {
      vector<int>freq(26,0), visited(26,0);
        for(auto ch:s)freq[ch-'a']++;

        string ans;
        int n = s.length();
        for(int i=0;i<n;i++){
               freq[s[i]-'a']--;
               if(!visited[s[i]-'a']){ 
                while(ans.size() and ans.back()>s[i] and freq[ans.back()-'a']>0) {
                    visited[ans.back()-'a'] = 0;
                    ans.pop_back();
                }
                ans.push_back(s[i]);
                visited[s[i]-'a'] = 1;
                }
        }
        return ans;
    }
};

Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a ⭐ star to the rishabhv12/Daily-Leetcode-Solution repository.