Welcome to Subscribe On Youtube
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); } } }
-
Todo
-
class Solution: def removeDuplicateLetters(self, s: str) -> str: last = {c: i for i, c in enumerate(s)} stk = [] vis = set() for i, c in enumerate(s): if c in vis: continue while stk and stk[-1] > c and last[stk[-1]] > i: vis.remove(stk.pop()) stk.append(c) vis.add(c) return ''.join(stk) ############ class Solution(object): def removeDuplicateLetters(self, s): """ :type s: str :rtype: str """ d = {} count = {} for c in s: d[c] = d.get(c, 0) + 1 count[c] = count.get(c, 0) + 1 stack = [] cache = set() for c in s: if c not in cache: while stack and stack[-1] > c and d[stack[-1]] > 1 and d[stack[-1]] != 1 and count[stack[-1]] > 0: cache.discard(stack.pop()) stack.append(c) cache.add(c) count[c] -= 1 return "".join(stack)