Dare2Solve
The task is to remove duplicate letters from a string so that every letter appears once and only once. The result should also be the smallest in lexicographical order among all possible results. You are required to maintain the relative order of the original characters.
To achieve the desired output, we need to ensure that each letter appears only once and that the resulting string is the smallest possible lexicographically. A stack-based approach works well in this situation because it allows us to make decisions about which characters to keep in a lexicographically sorted order while ensuring that we remove duplicates.
seen
) is used to track characters already in the stack.seen
set:
class Solution {
public:
string removeDuplicateLetters(string s) {
stack<char> st;
unordered_set<char> seen;
unordered_map<char, int> last_occurrence;
for (int i = 0; i < s.size(); i++) {
last_occurrence[s[i]] = i;
}
for (int i = 0; i < s.size(); i++) {
char ch = s[i];
if (seen.find(ch) == seen.end()) {
while (!st.empty() && st.top() > ch && last_occurrence[st.top()] > i) {
seen.erase(st.top());
st.pop();
}
st.push(ch);
seen.insert(ch);
}
}
string result = "";
while (!st.empty()) {
result = st.top() + result;
st.pop();
}
return result;
}
};
class Solution:
def removeDuplicateLetters(self, s: str) -> str:
stack = []
seen = set()
last_occurrence = {char: i for i, char in enumerate(s)}
for i, char in enumerate(s):
if char not in seen:
while stack and stack[-1] > char and last_occurrence[stack[-1]] > i:
seen.remove(stack.pop())
stack.append(char)
seen.add(char)
return ''.join(stack)
class Solution {
public String removeDuplicateLetters(String s) {
Stack<Character> stack = new Stack<>();
Set<Character> seen = new HashSet<>();
Map<Character, Integer> lastOccurrence = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
lastOccurrence.put(s.charAt(i), i);
}
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (!seen.contains(ch)) {
while (!stack.isEmpty() && stack.peek() > ch && lastOccurrence.get(stack.peek()) > i) {
seen.remove(stack.pop());
}
stack.push(ch);
seen.add(ch);
}
}
StringBuilder result = new StringBuilder();
while (!stack.isEmpty()) {
result.insert(0, stack.pop());
}
return result.toString();
}
}
var removeDuplicateLetters = function (s) {
const stack = [];
const seen = new Set();
for (let i = 0; i < s.length; i++) {
const char = s[i];
if (!seen.has(char)) {
while (
stack.length > 0 &&
stack[stack.length - 1] > char &&
s.indexOf(stack[stack.length - 1], i) > i
) {
seen.delete(stack.pop());
}
seen.add(char);
stack.push(char);
}
}
return stack.join('');
};