[LintCode/LeetCode] Remove Duplicate Letters

wanghui 发布于2019-08-15 18:01 / 3046人阅读

Problem

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example

Given "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"

Solution

public class Solution {
    /**
     * @param s: a string
     * @return: return a string
     */
    public String removeDuplicateLetters(String s) {
        // write your code here
        int[] count = new int[26]; // char-"a"
        char[] stack = new char[26]; // index
        boolean[] inStack = new boolean[26]; // char-"a"
        
        for (char ch: s.toCharArray()) count[ch-"a"]++;
        
        int index = 0;
        for (char ch: s.toCharArray()) {
            count[ch-"a"]--;
            if (!inStack[ch-"a"]) {
                //check the stack: if has larger element
                while (index > 0 && stack[index-1] > ch && count[stack[index-1]-"a"] > 0) {
                    index--;
                    inStack[stack[index]-"a"] = false;
                }
                stack[index++] = ch;
                inStack[ch-"a"] = true;
            }
        }
        return new String(stack, 0, index);
    }
}

服务器托管专线服务 Letters DUPLICATE remove remove()方法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69576.html

[LintCode/LeetCode] Subsets & Subsets II

Subsets Problem Given a set of distinct integers, return all possible subsets. Notice Elements in a subset must be in non-descending order.The solution set must not contain duplicate subsets. Example ...

tracy 2019-08-14 14:26 评论0 收藏0
[LintCode/LeetCode] Contains Duplicate II

Problem Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at ...

894974231 2019-08-19 10:48 评论0 收藏0
316. Remove Duplicate Letters and 402. Remove K Di

摘要：每个字母只留一个，而且保证字典序最小。从前往后扫描，还要往前看一个检出是否删除的，要用解。需要一个数据结构记录是否使用这个字母，可以用。结构也可以用数组加顶点指针模拟。 316 Remove Duplicate Given a string which contains only lowercase letters, remove duplicate letters so that e...

novo 2019-08-14 18:01 评论0 收藏0
LeetCode[316] Remove Duplicate Letters

摘要：复杂度思路用一个每次考虑当前的字符大小和的顶端字符的大小，如果当前字符比较小的话，则可以出顶端的字符，将当前的字符放进中。需要维持了一个判断当前字符在剩余字符串中的出现次数，考虑能否将这个字符从栈中弹出。 LeetCode[316] Remove Duplicate Letters Given a string which contains only lowercase letter...

tomorrowwu 2019-08-14 15:04 评论0 收藏0
[LintCode/LeetCode] Contains Duplicate III

Problem Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute dif...

MageekChiu 2019-08-19 10:48 评论0 收藏0