[Java] LeetCode 2405. Optimal Partition of String

[Java] LeetCode 2405. Optimal Partition of String

 

문   제 : 

String s 가 주어진다. s를 substring으로 나눈다.

나누는 조건은 다음과 같다.

   -  substring 안에서의 각 character들은 유니크 하다.

 

위와 같은 조건으로 s를 substring으로 나누었을 때, substring의 최소 개수를 구하여라.

 

 

Constraint

{ 1 <= s.length <= 10^5 }

{ s is only lowercase }

 

Matter

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.

 

Example )

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.

=========================================================================

Input: s = "ssssss"
Output: 6
Explanation:
The only valid partition is ("s","s","s","s","s","s").

 

 

---

접   근 : 

HashSet을 이용한 Greedy적 접근

---

해    결  &  설    명: 

substring의 개수를 저장하는 변수 : res

 

반복문을 돌면서 String s의 character를 하나 씩 확인한다.

 

HashSet을 선언하고 반환값이 true이면 계속 추가해나간다. (똑같은 글자가 추가되지 않을때까지)

 

만약 똑같은 글자가 나왔거나, 반복문의 범위가 s.length를 벗어났다면

HashSet에 추가하는 과정(substring을 늘리는 과정)을 멈춘다.

 

그리고 res++해준다.

 

---

결   과  :

class Solution {
    public int partitionString(String s) {
        int res=0;
        for(int i=0; i<s.length(); i++){
            Set<Character> set = new HashSet<>();
            set.add(s.charAt(i));
            
            while(i<s.length()-1 && set.add(s.charAt(i+1)) == true){
                i++;
            }
            res++;

        }

        return res;
    }
    
}