LeetCode in Kotlin

1081. Smallest Subsequence of Distinct Characters

Medium

Given a string s, return the lexicographically smallest subsequence of s that contains all the distinct characters of s exactly once.

Example 1:

Input: s = “bcabc”

Output: “abc”

Example 2:

Input: s = “cbacdcbc”

Output: “acdb”

Constraints:

• 1 <= s.length <= 1000
• s consists of lowercase English letters.

Note: This question is the same as 316: https://leetcode.com/problems/remove-duplicate-letters/

Solution

import java.util.Deque
import java.util.LinkedList

class Solution {
    fun smallestSubsequence(s: String): String {
        val n = s.length
        val stk: Deque<Char> = LinkedList()
        val freq = IntArray(26)
        val exist = BooleanArray(26)
        exist.fill(false)
        for (ch in s.toCharArray()) {
            freq[ch.code - 'a'.code]++
        }
        for (i in 0 until n) {
            val ch = s[i]
            freq[ch.code - 'a'.code]--
            if (exist[ch.code - 'a'.code]) {
                continue
            }
            while (stk.isNotEmpty() && stk.peek() > ch && freq[stk.peek().code - 'a'.code] > 0) {
                val rem = stk.pop()
                exist[rem.code - 'a'.code] = false
            }
            stk.push(ch)
            exist[ch.code - 'a'.code] = true
        }
        val ans = CharArray(stk.size)
        var index = 0
        while (stk.isNotEmpty()) {
            ans[index] = stk.pop()
            index++
        }
        return StringBuilder(String(ans)).reverse().toString()
    }
}

This site is open source. Improve this page.