Daily LeetCode Challenge - 2405. Optimal Partition of String

Problem From.
https://leetcode.com/problems/optimal-partition-of-string/

오늘 문제는 string s 가 주어질때, 그 string 의 substring 을 만들면서, substring 안의 알파벳들이 서로 겹치지 않도록 할 수 있는 substring 의 최소 갯수를 구하는 문제였다.

이 문제는 greedy algorithm 으로 접근했는데, s 의 앞에서부터 보면서 alpha set 안에 알파벳을 하나씩 넣으면서 중복이 있으면 정답 +1, 중복이 없으면 set 에 추가하고 넘어가는 식으로 구현하였다. Set 을 사용하여 중복을 거르고 contains 함수의 시간 복잡도가 O(1) 이므로 set 을 사용하였다.

class Solution {
    fun partitionString(s: String): Int {
        var answer = 0
        val alphaSet = mutableSetOf<Char>()
        s.forEach { alpha ->
            if(!alphaSet.contains(alpha)) {
                alphaSet.add(alpha)
            }else {
                answer += 1
                alphaSet.clear()
                alphaSet.add(alpha)
            }
        }
        if(alphaSet.isNotEmpty()) answer += 1
        return answer
    }
}