[LeetCode] 2405. Optimal Partition of String - Java

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

Optimal Partition of String - LeetCode

---

문제

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.

---

풀이

풀이 과정

알파벳 소문자로 이루어진 문자열 s가 주어질 때 문자열을 부분문자열들로 나누어 각 부분문자열에 중복된 글자가 존재하지 않는 부분문자열의 최소 개수를 구하는 문제이다.

정답을 저장할 변수를 선언하고 문자열의 길이가 최소 1이상이므로 1로 초기화한다.

// 최소 부분 문자열의 개수
// 문자열의 길이가 1이상이므로 1로 초기화
int answer = 1;

 

문자열을 부분문자열로 나눌 때 중복 사용된 글자를 판단하기 위해 Map을 사용한다.

// 문자열 탐색중 사용된 글자를 저장할 Map
Map<Character, Boolean> used = new HashMap<>();

 

문자열을 처음부터 탐색하며 각 글자를 Map에다 저장하고 Map에 저장된 글자가 사용된 경우, 즉 중복된 글자가 사용되는 경우에 그 부분에서 문자열을 나누고 정답 카운트를 증가시킨다.
모든 탐색이 종료된 후 구해진 정답을 return 한다.

// 문자열의 모든 글자를 탐색
for(int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);
    // 현재 탐색중인 글자가 Map에 포함되어 있는 경우 
    if(used.containsKey(c)){
        // 정답 카운트 증가
        answer++;
        // Map을 초기화 하고 현재 글자 추가
        used.clear();
        used.put(c, true);
    }
    // 현재 탐색중인 글자가 Map에 포함되어 있는 경우 
    else {
        // Map에 현재 글자 추가
        used.put(c, true);
    }
}

return answer;

---

최종 코드

class Solution {
    public int partitionString(String s) {
        // 최소 부분 문자열의 개수
        // 문자열의 길이가 1이상이므로 1로 초기화
        int answer = 1;
        // 문자열 탐색중 사용된 글자를 저장할 Map
        Map<Character, Boolean> used = new HashMap<>();
        
        // 문자열의 모든 글자를 탐색
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 현재 탐색중인 글자가 Map에 포함되어 있는 경우 
            if(used.containsKey(c)){
                // 정답 카운트 증가
                answer++;
                // Map을 초기화 하고 현재 글자 추가
                used.clear();
                used.put(c, true);
            }
            // 현재 탐색중인 글자가 Map에 포함되어 있는 경우 
            else {
                // Map에 현재 글자 추가
                used.put(c, true);
            }
        }

        return answer;
    }
}

---