資訊專欄INFORMATION COLUMN
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.
ExampleGiven "bcabc"
Return "abc"
Given "cbacdcbc"
Return "acdb"
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);
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/69576.html
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 ...
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 ...
摘要：每個(gè)字母只留一個(gè)，而且保證字典序最小。從前往后掃描，還要往前看一個(gè)檢出是否刪除的，要用解。需要一個(gè)數(shù)據(jù)結(jié)構(gòu)記錄是否使用這個(gè)字母，可以用。結(jié)構(gòu)也可以用數(shù)組加頂點(diǎn)指針模擬。 316 Remove Duplicate Given a string which contains only lowercase letters, remove duplicate letters so that e...
摘要：復(fù)雜度思路用一個(gè)每次考慮當(dāng)前的字符大小和的頂端字符的大小，如果當(dāng)前字符比較小的話，則可以出頂端的字符，將當(dāng)前的字符放進(jìn)中。需要維持了一個(gè)判斷當(dāng)前字符在剩余字符串中的出現(xiàn)次數(shù)，考慮能否將這個(gè)字符從棧中彈出。 LeetCode[316] Remove Duplicate Letters Given a string which contains only lowercase letter...
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...
閱讀 1918·2021-11-25 09:43
閱讀 1423·2021-11-22 14:56
閱讀 3288·2021-11-22 09:34
閱讀 2027·2021-11-15 11:37
閱讀 2282·2021-09-01 10:46
閱讀 1409·2019-08-30 15:44
閱讀 2305·2019-08-30 13:15
閱讀 2404·2019-08-29 13:07
