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

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.

풀이 시간

10분

난이도 쉬움

Constraints

• 1 <= s.length <= 16
• s contains only lower case English letters.

풀이 :
입력 문자 s를 분할하는데 전부 고유한 값으로 만들어야한다.

처음에는 DP쪽으로 생각하다가 문자열 길이가 최대 16개라 dfs로 간단하게 풀릴것 같다는 생각이 들었다.

import java.util.*;
class Solution {

    private int max;

    public int maxUniqueSplit(String s) {
        Stack<String> stack = new Stack<>();
        max = 0;
        dfs(stack, "", 0, s);
        return max;
    }

    private void dfs(Stack<String> stack, String pre, int idx, String s) {
        if (idx >= s.length()) {
            if (pre.isBlank()) {
                max = Math.max(max, stack.size());
            }
            return;
        }

        pre += s.charAt(idx);
        if (!stack.contains(pre)) {
            stack.push(pre);
            dfs(stack, "", idx + 1, s);
            stack.pop();
        }

        dfs(stack, pre, idx + 1, s);
    }
}