This approach uses a stack to build the resultant string such that it is the smallest lexicographical order. We will also use an array to keep count of each character’s frequency and a boolean array to track the characters that have been added to the stack. As we iterate over each character, we decide whether to add it to the stack or skip it based on the frequency and lexicographical conditions.
Time Complexity: O(n), where n is the length of the string, as each character is pushed and popped from the stack at most once.
Space Complexity: O(1), because the stack contains at most 26 characters, and other auxiliary data structures are of constant size.
1import java.util.Stack;
2
3public class Solution {
4 public String removeDuplicateLetters(String s) {
5 int[] freq = new int[26];
6 boolean[] inStack = new boolean[26];
7 for (char c : s.toCharArray()) freq[c - 'a']++;
8 Stack<Character> stack = new Stack<>();
9 for (char c : s.toCharArray()) {
10 freq[c - 'a']--;
11 if (inStack[c - 'a']) continue;
12 while (!stack.isEmpty() && stack.peek() > c && freq[stack.peek() - 'a'] > 0) {
13 inStack[stack.pop() - 'a'] = false;
14 }
15 stack.push(c);
16 inStack[c - 'a'] = true;
17 }
18 StringBuilder res = new StringBuilder();
19 for (char c : stack) res.append(c);
20 return res.toString();
21 }
22
23 public static void main(String[] args) {
24 Solution solution = new Solution();
25 System.out.println(solution.removeDuplicateLetters("cbacdcbc"));
26 }
27}This Java solution implements a similar approach using a stack along with arrays for frequency counting and tracking in-place characters. By continuously checking the top of the stack against the current character, we ensure the constructed string is the lexicographical minimum possible.
This approach focuses on iteratively constructing the result string while ensuring that the result remains lexicographically smallest by checking each character and including it in the result only if it meets certain frequency and order criteria.
Time Complexity: O(n), where n is the length of the input string.
Space Complexity: O(1), considering character storage is bounded to a maximum of 26.
1using System.Collections.Generic;
public class Solution {
public string RemoveDuplicateLetters(string s) {
int[] freq = new int[26];
bool[] used = new bool[26];
foreach (char c in s) freq[c - 'a']++;
Stack<char> result = new Stack<char>();
foreach (char c in s) {
freq[c - 'a']--;
if (used[c - 'a']) continue;
while (result.Count > 0 && result.Peek() > c && freq[result.Peek() - 'a'] > 0) {
used[result.Pop() - 'a'] = false;
}
result.Push(c);
used[c - 'a'] = true;
}
char[] res = result.ToArray();
Array.Reverse(res);
return new string(res);
}
public static void Main(string[] args) {
Solution solution = new Solution();
Console.WriteLine(solution.RemoveDuplicateLetters("cbacdcbc"));
}
}The C# iteration also utilizes add-on string crafting, preserving maximal character verification efficiency not compromising minimal space considerations in building results.