99클럽 코테 스터디 40일차 TIL + [LeetCode] 2405. Optimal Partition of String/그리디알고리즘/자바 풀이

 

 

 

 

 

 

1. 오늘의 학습 키워드

---

 

[LeetCode] 2405. Optimal Partition of String/그리디알고리즘/자바 풀이

 

 

2. 오늘의 학습 문제 

---

문제

---

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

 

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 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 <= 105
• s consists of only English lowercase letters.

 

코드

---

class Solution {
    public int partitionString(String s) {
        Set<Character> seen = new HashSet<>();
        int count = 0;
        
        for (char c : s.toCharArray()) {
            if (seen.contains(c)) {
                count++;
                seen.clear();
            }
            seen.add(c);
        }
        
        return count + 1;
    }
}

 

현재 문자가 set에 존재하는지 판단하여 count한다. 

 

3. 오늘의 회고

---

 

 

• 해쉬셋을 이용해 풀었다.