Smallest Subsequence with Distinct Characters
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