Split A String Into The Max Number Of Unique Substrings - Leetcode Solution

Problem Statement:

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

Solution:

To solve this problem, we can use a recursive approach. We can check if the current string is a unique substring and then recursively try to split the remaining part of the string. We can iterate over all possible substrings of the given string and check if that substring has already been used or not. If it is a unique substring, then we can recursively call the function on the remaining part of the string. We can keep track of the maximum number of unique substrings found so far and return it as the result.

To keep track of the used substrings, we can use a HashSet. We can add each new unique substring to the HashSet and use it to check if a particular substring has been used or not.

Code:

public int maxUniqueSubstr(String s) { HashSet<String> set = new HashSet<>(); int n = s.length(); int maxCount = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j <= n; j++) { String substr = s.substring(i, j); if (!set.contains(substr)) { set.add(substr); maxCount = Math.max(maxCount, 1 + maxUniqueSubstr(s.substring(j))); set.remove(substr); } } } return maxCount; }

Explanation:

The function maxUniqueSubstr takes a string s as input and returns the maximum number of unique substrings that the given string can be split into.

We first create a HashSet called set which we will use to store the unique substrings.

We then initialize the variable n with the length of the input string.

We then initialize the variable maxCount to 0 which we will use to store the maximum number of unique substrings found so far.

We then iterate over all possible substrings of the given string using two nested for loops. The outer loop iterates over the starting index of the substring and the inner loop iterates over the ending index of the substring.

For each substring, we check if it is already present in the HashSet using the contains method. If not, it means that this is a unique substring and we can add it to the HashSet and recursively call the function on the remaining part of the string starting from the next index.

We then update the maxCount variable to store the maximum number of unique substrings found so far. We then remove the current substring from the HashSet to prepare for the next iteration.

Finally, we return the maxCount variable which contains the maximum number of unique substrings that the given string can be split into.

This code has a time complexity of O(n^2) where n is the length of the input string. The space complexity is also O(n^2) due to the use of the HashSet to keep track of the unique substrings.

1