1593. Split a String Into the Max Number of Unique Substrings LeetCode Solution
In this guide, you will get 1593. Split a String Into the Max Number of Unique Substrings LeetCode Solution with the best time and space complexity. The solution to Split a String Into the Max Number of Unique Substrings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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.
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.
1593. Split a String Into the Max Number of Unique Substrings LeetCode Solution in C++
class Solution {
public:
int maxUniqueSplit(string s) {
size_t ans = 0;
dfs(s, 0, {}, ans);
return ans;
}
private:
void dfs(const string& s, int start, unordered_set<string>&& seen,
size_t& ans) {
if (start == s.length()) {
ans = max(ans, seen.size());
return;
}
for (int i = 1; start + i <= s.length(); ++i) {
const string cand = s.substr(start, i);
if (seen.contains(cand))
continue;
seen.insert(cand);
dfs(s, start + i, std::move(seen), ans);
seen.erase(cand);
}
}
}; /* code provided by PROGIEZ */
1593. Split a String Into the Max Number of Unique Substrings LeetCode Solution in Java
class Solution {
public int maxUniqueSplit(String s) {
dfs(s, 0, new HashSet<>());
return ans;
}
private int ans = 0;
private void dfs(final String s, int start, Set<String> seen) {
if (start == s.length()) {
ans = Math.max(ans, seen.size());
return;
}
for (int i = start + 1; i <= s.length(); ++i) {
final String cand = s.substring(start, i);
if (seen.contains(cand))
continue;
seen.add(cand);
dfs(s, i, seen);
seen.remove(cand);
}
}
} // code provided by PROGIEZ
1593. Split a String Into the Max Number of Unique Substrings LeetCode Solution in Python
