Home » leet code » Leetcode 316. Remove Duplicate Letters (Medium)

# Leetcode 316. Remove Duplicate Letters (Medium)

Leetcode 316. Remove Duplicate Letters : Hey there, coding enthusiasts! Welcome back to another exciting coding session. Today’s problem is a treat—literally! We’re going to solve the “Remove Duplicate Letters ” or “Leetcode 316.” problem.

Leet Code 287 Find the Duplicate Number (Medium)

## Approach Stack : Leetcode 316. Remove Duplicate Letters

Our Objective is, Leet code 316 presents a problem where the goal is to remove duplicate letters from a given string while preserving the original order of characters.

### Algorithm Overview:

1. We iterate through the input string and keep track of the last occurrence index of each character in the alphabet.
2. We use a stack to build the resulting string while making sure that the characters are in lexicographical order.
3. We maintain a boolean array to keep track of characters that we have already seen.

### Key Steps:

• Initialize a vector called `lastIndex` to store the last occurrence index of each character in the alphabet (26 letters).
• Initialize a vector called `seen` to keep track of the characters we have encountered.
• Use a stack (`st`) to build the result string while ensuring it’s in lexicographical order.

### Processing Steps:

• Iterate through the input string.
• For each character, check if it has been seen before. If it has, skip it as we aim to pick only one occurrence of each character.
• If the character is not in the stack (`st`), and there are characters in the stack that are greater than the current character, and there are more occurrences of those characters in the remaining string, remove them from the stack.
• Push the current character onto the stack and mark it as seen.
• Continue this process for all characters in the input string.

### Result:

• After processing all characters, the stack will contain the characters in the desired order.
• We build the final result string by popping characters from the stack and reversing it.
• By following this approach, we efficiently remove duplicate letters while maintaining the desired order, as required by Leetcode 316: Remove Duplicate Letter.

Below is Dry and Run of Approach. view both images for a clear understanding.

leet code to Ace the product based company

## Codes : Leetcode 316. Remove Duplicate Letters Stack Approach

### CPP / C++ : Stack Approach (Leet code 316.)

``````class Solution {
public:
string removeDuplicateLetters(string s) {
vector<int> lastIndex(26, 0);
for (int i = 0; i < s.length(); i++) {
lastIndex[s[i] - 'a'] = i; // track the lastIndex of character presence
}

vector<bool> seen(26, false); // keep track seen
stack<char> st;

for (int i = 0; i < s.size(); i++) {
int curr = s[i] - 'a';
if (seen[curr]) continue; // if seen, continue as we need to pick one char only
while (st.size() > 0 && st.top() > s[i] && i < lastIndex[st.top() - 'a']) {
seen[st.top() - 'a'] = false; // pop out and mark unseen
st.pop();
}
st.push(s[i]); // add into the stack
seen[curr] = true; // mark seen
}

string ans = "";
while (st.size() > 0) {
ans += st.top();
st.pop();
}
reverse(ans.begin(), ans.end());
return ans;
}
};

``````

### Java: Stack Approach (Leet code 316.)

``````import java.util.Stack;

class Solution {
public String removeDuplicateLetters(String s) {
int[] lastIndex = new int[26];
for (int i = 0; i < s.length(); i++) {
lastIndex[s.charAt(i) - 'a'] = i;
}

boolean[] seen = new boolean[26];
Stack<Character> st = new Stack<>();

for (int i = 0; i < s.length(); i++) {
int curr = s.charAt(i) - 'a';
if (seen[curr]) continue;
while (!st.isEmpty() && st.peek() > s.charAt(i) && i < lastIndex[st.peek() - 'a']) {
seen[st.pop() - 'a'] = false;
}
st.push(s.charAt(i));
seen[curr] = true;
}

StringBuilder ans = new StringBuilder();
while (!st.isEmpty()) {
ans.append(st.pop());
}
return ans.reverse().toString();
}
}``````

### Python 3: Stack Approach (Leet code 316.)

``````class Solution:
def removeDuplicateLetters(self, s: str) -> str:
lastIndex = [0] * 26
for i in range(len(s)):
lastIndex[ord(s[i]) - ord('a')] = i

seen = [False] * 26
st = []

for i in range(len(s)):
curr = ord(s[i]) - ord('a')
if seen[curr]:
continue
while st and st[-1] > s[i] and i < lastIndex[ord(st[-1]) - ord('a')]:
seen[ord(st.pop()) - ord('a')] = False
st.append(s[i])
seen[curr] = True

ans = ''.join(st)
return ans``````

### JavaScript: Stack Approach

``````/**
* @param {string} s
* @return {string}
*/
var removeDuplicateLetters = function(s) {
const lastIndex = new Array(26).fill(0);
for (let i = 0; i < s.length; i++) {
lastIndex[s.charCodeAt(i) - 'a'.charCodeAt(0)] = i;
}

const seen = new Array(26).fill(false);
const st = [];

for (let i = 0; i < s.length; i++) {
const curr = s.charCodeAt(i) - 'a'.charCodeAt(0);
if (seen[curr]) continue;
while (st.length > 0 && st[st.length - 1] > s[i] && i < lastIndex[st[st.length - 1].charCodeAt(0) - 'a'.charCodeAt(0)]) {
seen[st.pop().charCodeAt(0) - 'a'.charCodeAt(0)] = false;
}
st.push(s[i]);
seen[curr] = true;
}

let ans = '';
while (st.length > 0) {
ans += st.pop();
}
return ans.split('').reverse().join('');
}

``````

### Dart :Stack Approach (Leet code 316.)

``````class Solution {
String removeDuplicateLetters(String s) {
List<int> lastIndex = List.filled(26, 0);
for (int i = 0; i < s.length; i++) {
lastIndex[s.codeUnitAt(i) - 'a'.codeUnitAt(0)] = i;
}

List<bool> seen = List.filled(26, false);
List<String> st = [];

for (int i = 0; i < s.length; i++) {
int curr = s.codeUnitAt(i) - 'a'.codeUnitAt(0);
if (seen[curr]) continue;
while (st.isNotEmpty && st.last.compareTo(s[i]) > 0 && i < lastIndex[st.last.codeUnitAt(0) - 'a'.codeUnitAt(0)]) {
seen[st.removeLast().codeUnitAt(0) - 'a'.codeUnitAt(0)] = false;
}