[LeetCode] 1081. Smallest Subsequence of Distinct Characters

轉自LeetCode

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.

Solution

這題和 316. Remove Duplicate Letters 一模一樣，可以參考那篇

kotlin

	class Solution {
	fun removeDuplicateLetters(s: String): String {
	val map = mutableMapOf<Char,Int>()
	for(c in s) {
	map[c] = map[c]?.let{it+1} ?: 1
	}
	var ans = ""
	var set = mutableSetOf<Char>()
	for(c in s) {
	map[c] = map[c]!! - 1
	if (set.contains(c)) {
	continue
	}
	while(ans.isNotEmpty() && c < ans.last() && map[ans.last()]!! > 0) {
	set.remove(ans.last())
	ans = ans.dropLast(1)
	}
	ans += c
	set.add(c)
	}
	return ans
	}
	}

view raw remove_duplicate_letters.kt hosted with ❤ by GitHub