Jobs

Interviews

Discussions

Split a String Into the Max Number of Unique Substrings

Medium

Asked by:

More companies

28 views

Topics:

StringsRecursionGreedy Algorithms

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.

Try coding it in LeetCode

Split a String Into the Max Number of Unique Substrings

Medium

Asked by:

28 views

Topics:

StringsRecursionGreedy Algorithms

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

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string, and are there any constraints on the characters it may contain?
If it's not possible to split the string into unique substrings, what should the function return?
By 'substring', do you mean contiguous sequences of characters from the original string?
Are overlapping substrings allowed in the split? For example, could 'abab' be split into 'ab' and 'bab'?
Is there any preference if multiple valid splits into the maximum number of unique substrings exist?

Brute Force Solution

Approach

The brute force approach to splitting a string into the maximum number of unique substrings involves exploring every possible way to cut the string. We try all combinations of substrings and check if each combination meets the uniqueness requirement. Finally, we pick the combination that results in the most unique pieces.

Here's how the algorithm would work step-by-step:

Start by considering the very first character as its own substring. Then, consider the first two characters together, then the first three, and so on, up to the entire string.
For each of these initial substring possibilities, look at the remaining part of the string and repeat the same process: try each possible starting substring.
Every time you make a cut to create a new substring, check if that substring is different from all the previous substrings you've already created in that particular split.
If the new substring is not unique (it's the same as one you've already made), discard that splitting arrangement and try a different one.
If the new substring is unique, keep going and try to split the remaining portion of the string, repeating the same substring uniqueness checks.
Continue this process until the entire original string has been split into substrings.
Keep track of the number of unique substrings for each valid splitting arrangement you discover.
Once you've tried every possible splitting arrangement, compare the counts of unique substrings from each valid split. Select the split arrangement that produces the highest number of unique substrings. That's your answer.

Code Implementation

def max_unique_substrings(input_string):
    max_substring_count = 0

    def backtrack(start_index, current_substrings):
        nonlocal max_substring_count
        
        if start_index == len(input_string):
            # We have reached the end of the string, so update the max count.
            max_substring_count = max(max_substring_count, len(current_substrings))
            return

        for end_index in range(start_index + 1, len(input_string) + 1):
            substring = input_string[start_index:end_index]

            # Check if the substring is unique.
            if substring not in current_substrings:

                # Only explore further if the substring is unique.
                backtrack(end_index, current_substrings + [substring])

    backtrack(0, [])
    return max_substring_count

Big(O) Analysis

Time Complexity

O(2^n) – The algorithm explores all possible splits of the input string of length n. At each position in the string, we have a choice: either make a cut to form a new substring or don't. This binary choice at each of the n-1 possible cut points (between the n characters) leads to 2^(n-1) possible split combinations. Checking the uniqueness of each substring within each split further contributes to the cost, but the dominant factor is the exponential number of splits explored. Therefore, the time complexity is O(2^n).

Space Complexity

O(N) – The brute force approach, as described, uses recursion to explore all possible splits. In the worst-case scenario, the recursion depth can reach N, where N is the length of the input string, as we might consider each character as a separate substring. Each recursive call stores a set of the unique substrings found so far, which, in the worst case, could also contain up to N substrings of varying lengths. Thus, the space complexity is primarily dictated by the recursion depth and the storage of the substring set, leading to O(N) auxiliary space.

Optimal Solution

Approach

The best way to solve this problem is to greedily find the longest possible unique substring at each step. This means trying to carve out the biggest chunk we can, as long as it's unique, and then moving on to the rest of the string. This avoids exploring unnecessary options.

Here's how the algorithm would work step-by-step:

Start at the beginning of the string.
Try to create a substring of length 1, then length 2, then length 3, and so on, checking each time if the substring is already in our set of used substrings.
As soon as you find a substring that is not yet used, mark it as used and 'cut' it off from the original string.
Now, start again at the beginning of the remaining string, repeating the process.
Keep doing this until there's nothing left of the original string.
The total number of unique substrings you've found is the answer.

Code Implementation

def max_unique_substrings(input_string):
    used_substrings = set()
    substring_count = 0
    start_index = 0

    while start_index < len(input_string):
        current_substring_length = 1
        longest_unique_substring = ""

        while start_index + current_substring_length <= len(input_string):
            substring = input_string[start_index:start_index + current_substring_length]

            if substring not in used_substrings:
                longest_unique_substring = substring
            else:
                break

            current_substring_length += 1

        # If no unique substring, the loop breaks
        if not longest_unique_substring:
            break

        # Mark the longest unique substring as used.
        used_substrings.add(longest_unique_substring)

        substring_count += 1
        start_index += len(longest_unique_substring)

    return substring_count

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the string of length n. In each iteration, it tries to find the longest unique substring starting from the current position. This involves creating substrings of increasing lengths and checking if they exist in the set of used substrings. The substring check, in the worst case, could involve comparing the new substring of length at most n with other existing substrings, leading to n operations in the inner loop. Therefore, in the worst case, the algorithm might perform approximately n substring creation/comparison checks for each of the n positions in the string. Thus, the time complexity is approximately n * n/2, which simplifies to O(n²).

Space Complexity

O(N) – The algorithm utilizes a set (or similar data structure) to store the unique substrings encountered so far. In the worst-case scenario, each character could potentially form a unique substring of length 1, resulting in N unique substrings being stored. Thus, the space required for the set grows linearly with the input string's length, N. Therefore, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Empty input string	Return 0 as no substrings can be created.
Single character input string	Return 1 as the single character is a unique substring.
String with all same characters (e.g., 'aaaa')	Return 1 because the entire string is the only unique substring possible.
Long string with many repeating substrings	The backtracking search should handle this, although performance may be a concern so consider memoization.
String where no split results in unique substrings	The algorithm should return 1, using the entire string as the sole substring.
Maximum length string (due to constraints) leading to recursion depth issues	Ensure the recursion depth is limited or consider iterative approaches to avoid stack overflow.
String with a very long repeating prefix (e.g., 'ababababab')	Backtracking could get stuck exploring many fruitless splits before finding a better solution; memoization can help.
String that can be split in multiple ways to achieve the maximum number of unique substrings.	The algorithm needs to consistently return only one of these solutions since we are only looking for the maximum count.

Empty input string

How to Handle:

Return 0 as no substrings can be created.

Single character input string

How to Handle:

Return 1 as the single character is a unique substring.

String with all same characters (e.g., 'aaaa')

How to Handle:

Return 1 because the entire string is the only unique substring possible.

Long string with many repeating substrings

How to Handle:

The backtracking search should handle this, although performance may be a concern so consider memoization.

String where no split results in unique substrings

How to Handle:

The algorithm should return 1, using the entire string as the sole substring.

Maximum length string (due to constraints) leading to recursion depth issues

How to Handle:

Ensure the recursion depth is limited or consider iterative approaches to avoid stack overflow.

String with a very long repeating prefix (e.g., 'ababababab')

How to Handle:

Backtracking could get stuck exploring many fruitless splits before finding a better solution; memoization can help.

String that can be split in multiple ways to achieve the maximum number of unique substrings.

How to Handle:

The algorithm needs to consistently return only one of these solutions since we are only looking for the maximum count.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string, and are there any constraints on the characters it may contain?
If it's not possible to split the string into unique substrings, what should the function return?
By 'substring', do you mean contiguous sequences of characters from the original string?
Are overlapping substrings allowed in the split? For example, could 'abab' be split into 'ab' and 'bab'?
Is there any preference if multiple valid splits into the maximum number of unique substrings exist?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by considering the very first character as its own substring. Then, consider the first two characters together, then the first three, and so on, up to the entire string.
For each of these initial substring possibilities, look at the remaining part of the string and repeat the same process: try each possible starting substring.
Every time you make a cut to create a new substring, check if that substring is different from all the previous substrings you've already created in that particular split.
If the new substring is not unique (it's the same as one you've already made), discard that splitting arrangement and try a different one.
If the new substring is unique, keep going and try to split the remaining portion of the string, repeating the same substring uniqueness checks.
Continue this process until the entire original string has been split into substrings.
Keep track of the number of unique substrings for each valid splitting arrangement you discover.
Once you've tried every possible splitting arrangement, compare the counts of unique substrings from each valid split. Select the split arrangement that produces the highest number of unique substrings. That's your answer.

Code Implementation

def max_unique_substrings(input_string):
    max_substring_count = 0

    def backtrack(start_index, current_substrings):
        nonlocal max_substring_count
        
        if start_index == len(input_string):
            # We have reached the end of the string, so update the max count.
            max_substring_count = max(max_substring_count, len(current_substrings))
            return

        for end_index in range(start_index + 1, len(input_string) + 1):
            substring = input_string[start_index:end_index]

            # Check if the substring is unique.
            if substring not in current_substrings:

                # Only explore further if the substring is unique.
                backtrack(end_index, current_substrings + [substring])

    backtrack(0, [])
    return max_substring_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the beginning of the string.
Try to create a substring of length 1, then length 2, then length 3, and so on, checking each time if the substring is already in our set of used substrings.
As soon as you find a substring that is not yet used, mark it as used and 'cut' it off from the original string.
Now, start again at the beginning of the remaining string, repeating the process.
Keep doing this until there's nothing left of the original string.
The total number of unique substrings you've found is the answer.

Code Implementation

def max_unique_substrings(input_string):
    used_substrings = set()
    substring_count = 0
    start_index = 0

    while start_index < len(input_string):
        current_substring_length = 1
        longest_unique_substring = ""

        while start_index + current_substring_length <= len(input_string):
            substring = input_string[start_index:start_index + current_substring_length]

            if substring not in used_substrings:
                longest_unique_substring = substring
            else:
                break

            current_substring_length += 1

        # If no unique substring, the loop breaks
        if not longest_unique_substring:
            break

        # Mark the longest unique substring as used.
        used_substrings.add(longest_unique_substring)

        substring_count += 1
        start_index += len(longest_unique_substring)

    return substring_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input string	Return 0 as no substrings can be created.
Single character input string	Return 1 as the single character is a unique substring.
String with all same characters (e.g., 'aaaa')	Return 1 because the entire string is the only unique substring possible.
Long string with many repeating substrings	The backtracking search should handle this, although performance may be a concern so consider memoization.
String where no split results in unique substrings	The algorithm should return 1, using the entire string as the sole substring.
Maximum length string (due to constraints) leading to recursion depth issues	Ensure the recursion depth is limited or consider iterative approaches to avoid stack overflow.
String with a very long repeating prefix (e.g., 'ababababab')	Backtracking could get stuck exploring many fruitless splits before finding a better solution; memoization can help.
String that can be split in multiple ways to achieve the maximum number of unique substrings.	The algorithm needs to consistently return only one of these solutions since we are only looking for the maximum count.

Empty input string

How to Handle:

Return 0 as no substrings can be created.

Single character input string

How to Handle:

Return 1 as the single character is a unique substring.

String with all same characters (e.g., 'aaaa')

How to Handle:

Return 1 because the entire string is the only unique substring possible.

Long string with many repeating substrings

How to Handle:

The backtracking search should handle this, although performance may be a concern so consider memoization.

String where no split results in unique substrings

How to Handle:

The algorithm should return 1, using the entire string as the sole substring.

Maximum length string (due to constraints) leading to recursion depth issues

How to Handle:

Ensure the recursion depth is limited or consider iterative approaches to avoid stack overflow.

String with a very long repeating prefix (e.g., 'ababababab')

How to Handle:

Backtracking could get stuck exploring many fruitless splits before finding a better solution; memoization can help.

String that can be split in multiple ways to achieve the maximum number of unique substrings.

How to Handle:

The algorithm needs to consistently return only one of these solutions since we are only looking for the maximum count.