316. Remove Duplicate Letters
Medium
Given a string s
, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/
Example 1:
Input: s = "bcabc" Output: "abc"
Example 2:
Input: s = "cbacdcbc" Output: "acdb"
Constraints:
1 <= s.length <= 104
s
consists of lowercase English letters.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | class Solution { public: string removeDuplicateLetters(string s) { if(s.empty()) return s; string ret; while(!s.empty()){ int cnts[26] = {0}; for(char c:s) cnts[c-'a']++; int pos = 0, n = s.size(); for(int i=0; i<n; ++i){ if(s[i]<s[pos]) pos = i; cnts[s[i]-'a']--; //find who's the first to disappear if(cnts[s[i]-'a']==0) break; } ret += s[pos]; string next; for(int i=pos+1; i<n; ++i){ if(s[i]!=s[pos]) next += s[i]; } s = next; } return ret; } }; |
No comments:
Post a Comment