[LeetCode] 1593. Split a String Into the Max Number of Unique Substrings

https://leetcode.com/problems/split-a-string-into-the-max-number-of-unique-substrings/description/?envType=daily-question&envId=2024-10-21

leetcode - Split a String Into the Max Number of Unique Substrings

문제 유형: 백트래킹, 재귀, dfs, 해시, 문자열 처리

문제 난이도: Medium

 

문제

Given a string s, return the maximum number of unique substrings that the given string can be split into.

You can split string s into any list of non-empty substrings, where the concatenation of the substrings forms the original string. However, you must split the substrings such that all of them are unique.

A substring is a contiguous sequence of characters within a string.

 

문자열 s가 주어진다. 문자열을 나눠서 중복 없는 부분문자열들을 만들어 개수가 최대가 될 때, 그 개수를 구하시오.

당신은 길이가 1 이상인 부분문자열로 나눌 수 있습니다. 대시신, 중복되면 안됩니다.

 

풀이

백트래킹으로 해결할 수 있다.

우리는 실제 부분문자열 데이터의 값은 중요하지 않다. 우리가 주목할 것은, 그 문자열이 중복되지 않는지와 개수뿐이다.

해시 맵으로 존재여부를 빠르게 검색하도록 할 것이다.

 

solve(int idx, int count, string &s)를 실행한다.

idx는 부분문자열을 만들기 시작해야 하는 인덱스 부분, count는 현재 부분문자열 그룹의 개수를 추적한다.

만약 idx가 n보다 크거나 같다면, 최대거리를 갱신하고 리턴한다.

 

그렇지 않다면, 부분문자열을 만들어봐야 한다.

처음에는 s[idx]로 시작한다.

현재 그룹에 존재하지 않는다면, 해시맵에 있는 존재여부를 켜서 재귀호출하고, 그 호출이 돌아오고 나서는 해시맵에서 빼서 다시 돌려놓는다.

부분문자열 에는 s[idx+1]부터 해서 한글자씩 더해본다.

 

 

코드

C++

#pragma GCC optimize("03", "unrol-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
private:
    int ans;
    int n;
    unordered_map<string, int> exists;
    void solve(int idx, int count, string &s) {
        if(idx >= n) {
            ans = max(ans, count);
            return;
        }

        string temp = string(1, s[idx]);
        for(int i = idx+1; i <= n; ++i) {
            if(exists[temp] == 0) {
                exists[temp]++;
                solve(i, count+1, s);
                exists[temp]--;
            }
            temp += s[i];
        }
    }
public:
    int maxUniqueSplit(string s) {
        n = s.size();
        solve(0, 0, s);
        return ans;
    }
};