[LintCode/LeetCode] Remove Duplicate Letters

wanghui 發布于2019-08-15 18:01 / 3233人閱讀

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);
    }
}

GPU云服務器云服務器 Letters DUPLICATE remove remove()方法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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