Scale Engineer

Split a String Into the Max Number of Unique Substrings

Med
#1465Time: O(2^N * N), where N is the length of the string. There are `2^(N-1)` possible partitions. For each partition, we spend O(N) time to generate the substrings and check for uniqueness.Space: O(N), where N is the length of the string. We need to store the substrings for one partition at a time. The sum of the lengths of these substrings is always N.
Patterns
Backtracking
Data structures
Hash TableString

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This method systematically generates every possible partition of the string. A string of length N has N-1 potential positions for a split. We can use a bitmask of length N-1 to represent a partition: if the i-th bit is set, we split the string at index i. This results in 2^(N-1) total partitions. For each partition, we generate the list of substrings, check if they are all unique, and if so, we update the maximum number of substrings found in a valid partition.

Algorithm

  • Initialize max_splits = 1.
  • Let N be the length of the string s.
  • Iterate through a mask from 0 to 2^(N-1) - 1. Each mask represents a unique partition.
  • For each mask, generate the corresponding partition:
    • Create an empty list parts to store substrings.
    • Initialize last_cut_index = 0.
    • Iterate j from 0 to N-2:
      • If the j-th bit of the mask is 1, it signifies a cut after character j.
      • Add s.substring(last_cut_index, j + 1) to parts.
      • Update last_cut_index = j + 1.
    • Add the final substring s.substring(last_cut_index) to parts.
  • Check for uniqueness:
    • Create a HashSet from the parts list.
    • If the size of the set is equal to the size of the parts list, the partition is valid.
    • Update max_splits = max(max_splits, parts.size()).
  • Return max_splits.

Walkthrough

The core idea is to map each integer from 0 to 2^(N-1) - 1 to a unique partition of the string. We iterate through all these integers. For each integer, which acts as a bitmask, we build the corresponding list of substrings. A '1' at bit j in the mask signifies a cut after character j. After creating a list of substrings for a partition, we check its validity. A partition is valid if all its substrings are unique. This can be easily checked by inserting all substrings into a HashSet and comparing the set's size with the list's size. If the partition is valid, we update our global maximum with the number of substrings in this partition. This approach is exhaustive and guarantees finding the optimal solution, but it's inefficient as it explores many invalid partitions from start to finish.

class Solution {    public int maxUniqueSplit(String s) {        int n = s.length();        int maxCount = 0;        // Iterate through all 2^(n-1) partitions using a bitmask        for (int i = 0; i < (1 << (n - 1)); i++) {            List<String> substrings = new ArrayList<>();            int lastCut = 0;            for (int j = 0; j < n - 1; j++) {                // Check if the j-th bit is set, meaning a cut after index j                if ((i & (1 << j)) != 0) {                    substrings.add(s.substring(lastCut, j + 1));                    lastCut = j + 1;                }            }            // Add the last part of the string            substrings.add(s.substring(lastCut));             // Check for uniqueness            Set<String> uniqueSubstrings = new HashSet<>(substrings);            if (uniqueSubstrings.size() == substrings.size()) {                maxCount = Math.max(maxCount, substrings.size());            }        }        // If n > 0, maxCount will be at least 1 (the string itself)        return maxCount;    }}

Complexity

Time

O(2^N * N), where N is the length of the string. There are `2^(N-1)` possible partitions. For each partition, we spend O(N) time to generate the substrings and check for uniqueness.

Space

O(N), where N is the length of the string. We need to store the substrings for one partition at a time. The sum of the lengths of these substrings is always N.

Trade-offs

Pros

  • Conceptually simple and straightforward to implement.

  • Guaranteed to find the correct answer as it explores the entire solution space.

Cons

  • Highly inefficient due to its exponential time complexity.

  • It generates and checks many complete partitions that are invalid, performing redundant work that could be avoided.

Solutions

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);      }    }  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem