[Leetcode] 2405. Optimal Partition of String

문제 : https://leetcode.com/problems/optimal-partition-of-string/description/

---

문자열 s가 주어졌을 때, 각 부분 문자열에 중복되는 문자가 없도록 하나 이상의 부분 문자열로 분할합니다. 즉, 각 문자는 분할된 부분 문자열 안에 최대 하나만 속해야 합니다.

각 분할에서 최소한의 부분 문자열 수를 반환합니다.

 

---

그리디로 풀 수 있습니다.

알파벳이 부분 문자열 안에서 등장했는지를 저장하는 배열을 하나 만듭니다.

문자열을 앞에서부터 탐색하면서 해당 배열을 갱신해나갑니다.

만약 탐색중인 문자가 이미 등장했다면 배열을 다시 false로 초기화 시키고 부분 문자열 수를 하나 증가시킵니다.

모든 문자열을 탐색했을 때 부분 문자열 수가 정답이 됩니다.

 

시간복잡도는 O(N). 공간복잡도는 O(1).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/2405.%20Optimal%20Partition%20of%20String.cpp