Remove Duplicate Letters

Leetcode Problem 316: Remove Duplicate Letters

Problem Summary

Given a string s, remove duplicate letters so that every letter appears exactly once. Among all possible results, return the one that is lexicographically smallest while still being a subsequence of the original string.

Constraints:

• The string has between 1 and 10,000 characters, consisting of lowercase English letters only.

Techniques

• String
• Stack
• Greedy
• Monotonic Stack

Solution

function removeDuplicateLetters(s: string): string {
    let lastPositionOfChars = new Map<string, number>()

    for (let i = 0; i < s.length; i++) {
        lastPositionOfChars.set(s.charAt(i), i)
    }

    let alreadyUsed = new Set<string>()
    let result = "" //This is basically a monothonic stack

    for (let i = 0; i < s.length; i++) {
        let currentChar = s.charAt(i)
        let topChar = result.charAt(result.length - 1)

        if (!alreadyUsed.has(currentChar) && currentChar > topChar) {
            result += currentChar
        }

        if (!alreadyUsed.has(currentChar) && currentChar < topChar) {
            while ((lastPositionOfChars.get(topChar) ?? -1) > i && topChar > currentChar) {
                result = result.substring(0, result.length - 1);
                alreadyUsed.delete(topChar)
                topChar = result.charAt(result.length - 1)
            }

            result += currentChar
        }

        alreadyUsed.add(currentChar)
    }

    return result
};