Algorithm
Problem Name: 316. Remove Duplicate Letters
Problem Link: https://leetcode.com/problems/remove-duplicate-letters/
Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is
Example 1:
Input: s = "bcabc" Output: "abc"
Example 2:
Input: s = "cbacdcbc" Output: "acdb"
Constraints:
1 <= s.length <= 104sconsists of lowercase English letters.
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public String removeDuplicateLetters(String s) {
int[] counter = new int[26];
for (char c : s.toCharArray()) {
counter[c - 'a']++;
}
Stack < Integer> stack = new Stack<>();
boolean[] visited = new boolean[26];
for (char c : s.toCharArray()) {
int idx = c - 'a';
counter[idx]--;
if (visited[idx]) {
continue;
}
while (!stack.isEmpty() && stack.peek() > idx && counter[stack.peek()] > 0) {
visited[stack.pop()] = false;
}
stack.add(idx);
visited[idx] = true;
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append((char) (stack.pop() + 'a'));
}
return sb.reverse().toString();
}
}
Input
s = "bcabc"
Output
"abc"
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const removeDuplicateLetters = function(s) {
const last = {}
for (let i = 0; i < s.length; i++) last[s.charAt(i)] = i
const added = {}
const stack = []
for (let i = 0; i < s.length; i++) {
const char = s.charAt(i)
if (added[char]) continue
while (stack.length && char < stack[0] && last[stack[0]] > i) {
added[stack[0]] = false
stack.shift()
}
stack.unshift(char)
added[char] = true
}
return stack.reverse().join('')
}
Input
s = "bcabc"
Output
"abc"
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def removeDuplicateLetters(self, s):
rindex = {c: i for i, c in enumerate(s)}
result = ''
for i, c in enumerate(s):
if c not in result:
while c < result[-1:] and i < rindex[result[-1]]:
result = result[:-1]
result += c
return result
Input
s = "cbacdcbc"
Output
"acdb"
#4 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _0316_RemoveDuplicateLetters
{
public string RemoveDuplicateLetters(string s)
{
var indexes = new Dictionary < char, int>();
for (int i = 0; i < s.Length; i++)
indexes[s[i]] = i;
var seen = new HashSet < char>();
var stack = new Stack();
for (int i = 0; i < s.Length; i++)
{
var ch = s[i];
if (!seen.Contains(ch))
{
while (stack.Count > 0 && stack.Peek() > ch && i < indexes[stack.Peek()])
seen.Remove(stack.Pop());
seen.Add(ch);
stack.Push(ch);
}
}
var str = new char[stack.Count];
int index = stack.Count - 1;
foreach (var ch in stack)
str[index--] = ch;
return new string(str);
}
}
}
Input
s = "cbacdcbc"
Output
"acdb"