Time: 32 ms (77.78%), Space: 44.5 MB (92.16%) - LeetHub

py3-coder · py3-coder · commit 0cd45c1a1b10 · 2024-10-21T23:16:12.000+05:30
diff --git a/1593-split-a-string-into-the-max-number-of-unique-substrings/1593-split-a-string-into-the-max-number-of-unique-substrings.java b/1593-split-a-string-into-the-max-number-of-unique-substrings/1593-split-a-string-into-the-max-number-of-unique-substrings.java
@@ -0,0 +1,25 @@
+class Solution {
+     public int maxUniqueSplit(String s) {
+        int[] res = new int[1];
+        Set<String> set = new HashSet<>();
+        
+        dfs(res, s, set, 0);
+        return res[0];
+    }
+    
+    private void dfs(int[] res, String s, Set<String> set, int cur) {
+        if (cur == s.length()) {
+            res[0] = Math.max(res[0], set.size());
+            return;
+        }
+        
+        for (int i = cur; i < s.length(); i++) {
+            String word = s.substring(cur, i + 1);
+            if (!set.contains(word)) {
+                set.add(word);
+                dfs(res, s, set, i + 1);
+                set.remove(word);
+            }
+        }
+    }
+}
