Smallest Subsequence with Distinct Characters
The goal is to find the lexicographically smallest subsequence with no repeated characters from an alphabetic string.
Two key constraints here: we want the lexicographically smallest result, and we need a subsequence (which means we preserve the original order). So we scan left to right.
To get the lexicographically smallest result, we use a greedy approach. If the last character in our current subsequence could be smaller and that larger character appears again later, we remove it first. We use fixed-size arrays to track character counts and usage.
Time complexity: O(N) Space complexity: O(1)
string smallestSubsequence(string text) {
int count[26] = {};
int used[26] = {};
// Count all characters
for(auto c : text) ++count[c-'a'];
string res = "";
for(auto c : text) {
// Skip if already used
if (used[c-'a']) {
--count[c-'a'];
continue;
}
// Remove larger characters that appear again later
while(!res.empty() && c < res.back() && count[res.back()-'a']>0) {
used[res.back()-'a']=false;
res.pop_back();
}
// Add current character
used[c-'a'] = true;
--count[c-'a'];
res.push_back(c);
}
return res;
}#string #greedy