LeetCode Remove Duplicate Letters
原题链接在这里:https://leetcode.com/problems/remove-duplicate-letters/
题目:
Given a string which contains only lowercase letters, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
Example 1:
Input:"bcabc"
Output:"abc"
Example 2:
Input:"cbacdcbc"
Output:"acdb"
题解:
Mark the last appearance of each char in s.
For current char, if it is not added in stack.
Keep checking the last added char, if it is bigger than current char and its last appearence is after current index i. Then it could be added later.
Pop it out and mark it unused.
Eventually the chars in stack are expected result.
Time Complexity: O(n). = s.length().
Space: O(1).
AC Java:
class Solution {
public String removeDuplicateLetters(String s) {
int [] last = new int[26];
for(int i = 0; i<s.length(); i++){
last[s.charAt(i)-'a'] = i;
} Stack<Character> stk = new Stack<>();
boolean [] used = new boolean[26];
for(int i = 0; i<s.length(); i++){
char c = s.charAt(i);
if(used[c-'a']){
continue;
} while(!stk.isEmpty() && stk.peek()>c && last[stk.peek()-'a']>i){
char top = stk.pop();
used[top-'a'] = false;
} stk.push(c);
used[c-'a'] = true;
} StringBuilder sb = new StringBuilder();
for(char c : stk){
sb.append(c);
} return sb.toString();
}
}
类似Smallest Subsequence of Distinct Characters.
最新文章
- Ubuntu 14.04 更换阿里云源
- dev_set_draw的fill和margin模式
- 解决phpMyAdmin“登录超时 (1440 秒未活动),请重新登录”的问题
- excel具有制作甘特图的功能
- mvc学习记录
- Insert后返回自动插入的生成的ID:select @@identity
- QT Creator 2.7.2 代码自动补全快捷键设置
- codeblocks + MinGW 以及vc 使用预编译头文件的方法
- 将鼠标移到文本弹出一些字幕CSS达到,不及格JS达到
- neo4j 数据库导入导出
- sqlServer遇到的问题
- Python学习--Python运算符
- 原生JS实现选中的radio变为未选中
- flash中调用XML遇到的中文显示异常问题
- Debian Buster 配置 Laravel 运行环境(nginx + redis + supervisor)
- .net core 滑动+点击汉字验证码
- android学习-数据存储(一)-----SQLite源码分析
- futuba R70085SB 接收机 只有SBus端口有输出其他端口输出不变
- 使用开源库 MBProgressHUD 等待指示器
- MYC编译器源码分析之程序入口