Leetcode 316. Remove Duplicate Letters (Medium) : NileshBlog.Tech

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)

Table of Contents

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:

We iterate through the input string and keep track of the last occurrence index of each character in the alphabet.

We use a stack to build the resulting string while making sure that the characters are in lexicographical order.
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.

Runaway Jedi : Language task in VSCode 2023

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.

Leetcode 316. Remove Duplicate Letters Appraoch — **Leetcode 316. Remove Duplicate Letter Appraoch**

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;
      }
      st.add(s[i]);
      seen[curr] = true;
    }

    String ans = '';
    while (st.isNotEmpty) {
      ans += st.removeLast();
    }
    return ans.split('').reversed.join('');
  }
}

List of Some important Leet code Question :