Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

去除重复字母 #246

Open
louzhedong opened this issue Apr 24, 2021 · 0 comments
Open

去除重复字母 #246

louzhedong opened this issue Apr 24, 2021 · 0 comments

Comments

@louzhedong
Copy link
Owner

习题

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

注意:该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters 相同

示例 1:

输入:s = "bcabc"
输出:"abc"
示例 2:

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

提示:

1 <= s.length <= 104
s 由小写英文字母组成

思路

  1. 创建一个map统计s中每个字母出现的次数
  2. 创建一个栈维护字典序最小的字符串序列
  3. 遍历字符串,出现的字符map统计-1
  4. 如果当前字符未在栈中,则需要将当前字符推入栈
  5. 在推入栈时,需要判断栈顶的元素的字典序是否比当前字符大,如果大于当前字符且s中还存在另外的栈顶元素,则将该元素pop

解答

javascript

/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicateLetters = function(s) {
   var map = new Map(), stack = [];
   for(var i = 0, length = s.length; i < length; i  ) {
       var current = s[i];
       if (map.get(current)) {
           map.set(current, map.get(current)   1);
       } else {
           map.set(current, 1);
       }
   }

    for (var i = 0, length = s.length; i < length; i  ) {
        var current = s[i];
        map.set(current, map.get(current) - 1);
        if (stack.includes(current) == false) {
            var j = stack.length;
            while(j-- && stack[j] > current && map.get(stack[j])) {
                stack.pop();
            }
            stack.push(current);
        }
    }
    return stack.join('');
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant