# 26.09.2023 [316. Remove Duplicate Letters]
Lexicographical smallest subsequence without duplicates
26.09.2023
316. Remove Duplicate Letters medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/351
Problem TLDR
Lexicographical smallest subsequence without duplicates
Intuition
The brute force way would be to just consider every position and do a DFS.
To pass the test case, however, there is a greedy way: let’s take characters and pop them if new is smaller and the duplicate exists later in a string.
// 01234
// 234
// bcabc
// * b
// * bc
// * a, pop c, pop b
// * ab
// * abc
Approach
We can use Kotlin’s buildString
API instead of a Stack
Complexity
Time complexity:
O(n)Space complexity:
O(1)
Code
fun removeDuplicateLetters(s: String) = buildString {
var visited = mutableSetOf<Char>()
val lastInds = mutableMapOf<Char, Int>()
s.onEachIndexed { i, c -> lastInds[c] = i}
s.onEachIndexed { i, c ->
if (visited.add(c)) {
while (isNotEmpty() && last() > c && i < lastInds[last()]!!)
visited.remove(last()).also { setLength(lastIndex) }
append(c)
}
}
}