nikunjsoni

1081

Mar 29th, 2021
81
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     string smallestSubsequence(string s) {
  4.         string ans =  "";
  5.         int last[26] = {0};
  6.         int seen[26] = {0};
  7.        
  8.         for(int i=0; i<s.length(); i++){
  9.             last[s[i]-'a'] = i;
  10.         }
  11.        
  12.         for(int i=0; i<s.length(); i++){
  13.             if(seen[s[i]-'a']) continue;
  14.             while(!ans.empty() && ans.back() > s[i] && last[ans.back()-'a'] > i){
  15.                 seen[ans.back()-'a']--;
  16.                 ans.pop_back();
  17.             }
  18.             ans.push_back(s[i]);
  19.             seen[s[i]-'a']++;
  20.         }
  21.         return ans;
  22.     }
  23. };
RAW Paste Data