LeetCode Entry

316. Remove Duplicate Letters

26.09.2023 medium 2023 kotlin

Lexicographical smallest subsequence without duplicates

316. Remove Duplicate Letters medium blog post substack image.png

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)
        }
      }
    }