Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1593.html
1593. Split a String Into the Max Number of Unique Substrings (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.
Example 1:
Input: s = "ababccc" Output: 5 Explanation: One way to split maximally is ['a', 'b', 'ab', 'c', 'cc']. Splitting like ['a', 'b', 'a', 'b', 'c', 'cc'] is not valid as you have 'a' and 'b' multiple times.
Example 2:
Input: s = "aba" Output: 2 Explanation: One way to split maximally is ['a', 'ba'].
Example 3:
Input: s = "aa" Output: 1 Explanation: It is impossible to split the string any further.
Constraints:
-
1 <= s.length <= 16
-
s
contains only lower case English letters.
Related Topics:
Backtracking
Solution 1. Backtrack
// OJ: https://leetcode.com/problems/split-a-string-into-the-max-number-of-unique-substrings/
// Time: O(2^N)
// Space: O(N)
class Solution {
unordered_set<string> m;
int ans = 0;
void dfs(string &s, int i) {
if (i == s.size()) {
ans = max(ans, (int)m.size());
return;
}
for (int j = i; j < s.size(); ++j) {
string sub = s.substr(i, j - i + 1);
if (m.count(sub)) continue;
m.insert(sub);
dfs(s, j + 1);
m.erase(sub);
}
}
public:
int maxUniqueSplit(string s) {
dfs(s, 0);
return ans;
}
};
-
class Solution { public int maxUniqueSplit(String s) { int length = s.length(); if (length == 1) return 1; int maxSplit = 1; int total = 1 << (length - 1); for (int i = 1; i < total; i++) { boolean[] split = new boolean[length - 1]; int mask = i; int splitCount = 1; for (int j = 0; j < length - 1 && mask > 0; j++) { if (mask % 2 == 1) { split[j] = true; splitCount++; } mask /= 2; } if (splitCount > maxSplit && checkUnique(s, split, splitCount)) maxSplit = splitCount; } return maxSplit; } public boolean checkUnique(String s, boolean[] split, int splitCount) { Set<String> set = new HashSet<String>(); int start = 0; int length = s.length(); for (int i = 0; i < length - 1; i++) { if (split[i]) { set.add(s.substring(start, i + 1)); start = i + 1; } } if (start < length) set.add(s.substring(start)); return set.size() == splitCount; } } ############ class Solution { private Set<String> vis = new HashSet<>(); private int ans = 1; private String s; public int maxUniqueSplit(String s) { this.s = s; dfs(0, 0); return ans; } private void dfs(int i, int t) { if (i >= s.length()) { ans = Math.max(ans, t); return; } for (int j = i + 1; j <= s.length(); ++j) { String x = s.substring(i, j); if (vis.add(x)) { dfs(j, t + 1); vis.remove(x); } } } }
-
// OJ: https://leetcode.com/problems/split-a-string-into-the-max-number-of-unique-substrings/ // Time: O(2^N) // Space: O(N) class Solution { unordered_set<string> m; int ans = 0; void dfs(string &s, int i) { if (i == s.size()) { ans = max(ans, (int)m.size()); return; } for (int j = i; j < s.size(); ++j) { string sub = s.substr(i, j - i + 1); if (m.count(sub)) continue; m.insert(sub); dfs(s, j + 1); m.erase(sub); } } public: int maxUniqueSplit(string s) { dfs(s, 0); return ans; } };
-
class Solution: def maxUniqueSplit(self, s: str) -> int: def dfs(i, t): if i >= len(s): nonlocal ans ans = max(ans, t) return for j in range(i + 1, len(s) + 1): if s[i:j] not in vis: vis.add(s[i:j]) dfs(j, t + 1) vis.remove(s[i:j]) vis = set() ans = 1 dfs(0, 0) return ans ############ # 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/ class Solution: def maxUniqueSplit(self, S: str) -> int: def backtrack(S, seen): res = 0 for i in range(1,len(S)+1): s = S[:i] if s not in seen: seen.add(s) res = max(res, 1 + backtrack(S[i:], seen)) seen.remove(s) return res seen = set() return backtrack(S, seen)
-
func maxUniqueSplit(s string) int { ans := 1 vis := map[string]bool{} var dfs func(i, t int) dfs = func(i, t int) { if i >= len(s) { ans = max(ans, t) return } for j := i + 1; j <= len(s); j++ { x := s[i:j] if !vis[x] { vis[x] = true dfs(j, t+1) vis[x] = false } } } dfs(0, 0) return ans } func max(a, b int) int { if a > b { return a } return b }