LeetCode 316: Remove Duplicate Letters
LeetCode 316 Solution Explanation
Explanation
To solve this problem, we can use a stack to maintain the characters of the final result. We iterate through the input string s and for each character:
- If the character is already present in the stack, we skip it.
- If the character is smaller than the top of the stack and the top of the stack will occur later in the string again, we pop the top of the stack.
- Finally, we push the current character onto the stack.
This way, we ensure that the result is the smallest lexicographical order and has distinct characters.
Time Complexity: O(n), where n is the length of the input string. Space Complexity: O(1) since the stack will contain at most 26 characters.
LeetCode 316 Solutions in Java, C++, Python
class Solution {
public String removeDuplicateLetters(String s) {
Stack<Character> stack = new Stack<>();
int[] count = new int[26];
boolean[] visited = new boolean[26];
for (char c : s.toCharArray()) {
count[c - 'a']++;
}
for (char c : s.toCharArray()) {
count[c - 'a']--;
if (visited[c - 'a']) {
continue;
}
while (!stack.isEmpty() && c < stack.peek() && count[stack.peek() - 'a'] > 0) {
visited[stack.pop() - 'a'] = false;
}
stack.push(c);
visited[c - 'a'] = true;
}
StringBuilder sb = new StringBuilder();
for (char c : stack) {
sb.append(c);
}
return sb.toString();
}
}Interactive Code Editor for LeetCode 316
Improve Your LeetCode 316 Solution
Use the editor below to refine the provided solution for LeetCode 316. Select a programming language and try the following:
- Add import statements if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.
Loading editor...