[LeetCode][Kotlin] 2405. Optimal Partition of String

2405. Optimal Partition of String

Given a string s, partition the string into one or more substrings such that the characters in each substring are unique. That is, no letter appears in a single substring more than once.

 

Return the minimum number of substrings in such a partition.

 

Note that each character should belong to exactly one substring in a partition.

문자열 s가 주어지면 각 부분 문자열의 문자가 고유하도록 문자열을 하나 이상의 부분 문자열로 분할합니다. 즉, 단일 하위 문자열에 문자가 두 번 이상 나타나지 않습니다. 

그러한 파티션에 있는 부분 문자열의 최소 개수를 반환합니다. 

각 문자는 파티션의 정확히 하나의 하위 문자열에 속해야 합니다.

 

Example 1:

Input: s = "abacaba"

Output: 4

Explanation:

Two possible partitions are ("a","ba","cab","a") and ("ab","a","ca","ba").

It can be shown that 4 is the minimum number of substrings needed.

 

Example 2:

Input: s = "ssssss"

Output: 6

Explanation:

The only valid partition is ("s","s","s","s","s","s").

 

Constraints:

• 1 <= s.length <= 10^5
• s consists of only English lowercase letters.

---

코드 1

class Solution {
    fun partitionString(s: String): Int {
        val hs = HashSet<Char>()
        var answer = 0

        s.forEach { c ->
            if (c in hs) {
                answer++
                hs.clear()
            }
            hs.add(c)
        }

        return if (hs.size != 0) answer + 1 else answer
    }
}

 

코드 2

class Solution {
    fun partitionString(s: String): Int {
        var answer = 0
        var alpha = IntArray(26)

        s.forEach { c ->
            if (alpha[c - 'a'] == 1) {
                answer++
                alpha = IntArray(26)
            }
            alpha[c - 'a'] = 1
        }

        if (alpha.any { it == 1 }) {
            answer++
        }

        return answer
    }
}