去除重复字母

Tips

题目类型: 单调栈

题目

给你一个字符串 s, 请你去除字符串中重复的字母, 使得每个字母只出现一次.需保证返回结果的字典序最小(要求不能打乱其他字符的相对位置).

示例

输入: s = 'bcabc'
输出: 'abc'

输入: s = 'cbacdcbc'
输出: 'acdb'

题解

首先用 hashmap 收集 s 中每个元素的个数
使用单调栈, 具体看注释, 这道题去掉元素的方法跟 402. 移掉 k 位数字一致, 都是栈尾元素比当前元素大, 栈尾元素就应该被当前元素替换

JavaScript
Rust

/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicateLetters = function (s) {
  const remain = new Map()
  for (const letter of s) {
    if (remain.has(letter)) {
      remain.set(letter, remain.get(letter) + 1)
    } else {
      remain.set(letter, 1)
    }
  }

  const stack = []
  for (const letter of s) {
    // 保证栈中不会出现重复元素
    if (!stack.includes(letter)) {
      // 单调栈保证按字典序最小
      while (
        stack.length !== 0 &&
        // 如果栈尾元素比当前元素大, 栈尾元素就应该被当前元素替换
        stack[stack.length - 1].charCodeAt() > letter.charCodeAt() &&
        // 当然如果栈尾元素的个数已经为零了, 这个元素也不能被替换
        remain.get(stack[stack.length - 1]) > 0
      ) {
        stack.pop()
      }
      stack.push(letter)
    }

    // 循环往右走, 意味着当前元素的剩余量也会减 1, 到最后 remain 里所有元素的值都为 0
    remain.set(letter, remain.get(letter) - 1)
  }

  return stack.join('')
}

use std::collections::HashMap;

pub fn remove_duplicate_letters(s: String) -> String {
    let mut remain = HashMap::new();

    for char in s.as_bytes() {
        remain.entry(char).and_modify(|e| *e += 1).or_insert(1);
    }

    let mut stack = vec![];

    for char in s.as_bytes() {
        if !stack.contains(char) {
            while !stack.is_empty()
                && stack[stack.len() - 1] > *char
                && remain.get(&stack[stack.len() - 1]).unwrap() > &0
            {
                stack.pop();
            }

            stack.push(*char);
        }

        remain.entry(char).and_modify(|e| *e -= 1);
    }

    stack.iter().map(|&s| s as char).collect::<String>()
}

题目​

题解​

题目

题解