Question
Formatted question description: https://leetcode.ca/all/316.html
316 Remove Duplicate Letters
Given a string which contains only lowercase letters,
remove duplicate letters so that every letter appears once and only once.
You must make sure your result is the smallest in lexicographical order among all possible results.
Example 1:
Input: "bcabc"
Output: "abc"
Example 2:
Input: "cbacdcbc"
Output: "acdb"
@tag-stack
@tag-string
Algorithm
First use the hash table to record the number of occurrences of each letter, and then traverse the given string s to find the smallest letter. For each letter compared, the value in the hash table is reduced by 1. If it is 0 at this time, then Do-not continue traversing, at this time we recorded a position, delete all the characters on the left of that position in the string s, and delete all the reappearing letters on the right.
Just call this function recursively. Use replaceAll()
function.
Code
Java
public class Remove_Duplicate_Letters {
public static void main(String[] args) {
Remove_Duplicate_Letters out = new Remove_Duplicate_Letters();
Solution s = out.new Solution();
System.out.println(s.removeDuplicateLetters("cbacdcbc")); // acdb
}
// greedy. The runtime is O(26 * n) = O(n).
public class Solution {
// @todo: stack solution
public String removeDuplicateLetters(String s) {
/*
System.out.println(s);
cbacdcbc
cdcbc
db
b
*/
if (s.length() == 0) {
return "";
}
int[] cnt = new int[26];
int pos = 0; // the position for the smallest s[i]
// count char freq
for (int i = 0; i < s.length(); i++) {
cnt[s.charAt(i) - 'a']++;
}
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) < s.charAt(pos)) {
pos = i;
}
// find first char down to 0
// s[i] could be not s[pos], like `cdcbc`
// because need to lexicographical, any char before ==0 char need to be included
if (--cnt[s.charAt(i) - 'a'] == 0) {
break;
}
}
String rightSideString = s.substring(pos + 1);
String next = rightSideString.replaceAll("" + s.charAt(pos), "");
return s.charAt(pos) + removeDuplicateLetters(next);
}
}
}