Maximum Number of Non-Overlapping Substrings

Hard

#1401Time: O(N^3), where N is the length of the string. Generating all O(N^2) substrings and validating each in O(N) time results in an O(N^3) complexity.Space: O(N^2), where N is the length of the string. In the worst-case scenario, we might need to store O(N^2) valid intervals.

Patterns

Greedy

Data structures

String

Prompt

Given a string s of lowercase letters, you need to find the maximum number of non-empty substrings of s that meet the following conditions:

The substrings do not overlap, that is for any two substrings s[i..j] and s[x..y], either j < x or i > y is true.
A substring that contains a certain character c must also contain all occurrences of c.

Find the maximum number of substrings that meet the above conditions. If there are multiple solutions with the same number of substrings, return the one with minimum total length. It can be shown that there exists a unique solution of minimum total length.

Notice that you can return the substrings in any order.

Example 1:

Input: s = "adefaddaccc"
Output: ["e","f","ccc"]
Explanation: The following are all the possible substrings that meet the conditions:
[
  "adefaddaccc"
  "adefadda",
  "ef",
  "e",
  "f",
  "ccc",
]
If we choose the first string, we cannot choose anything else and we'd get only 1. If we choose "adefadda", we are left with "ccc" which is the only one that doesn't overlap, thus obtaining 2 substrings. Notice also, that it's not optimal to choose "ef" since it can be split into two. Therefore, the optimal way is to choose ["e","f","ccc"] which gives us 3 substrings. No other solution of the same number of substrings exist.

Example 2:

Input: s = "abbaccd"
Output: ["d","bb","cc"]
Explanation: Notice that while the set of substrings ["d","abba","cc"] also has length 3, it's considered incorrect since it has larger total length.

Constraints:

1 <= s.length <= 10⁵
s contains only lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves a straightforward, brute-force method. It begins by systematically generating every possible substring of the input string s. For each substring, it checks if it meets the specified 'character completeness' condition. All substrings that satisfy this condition are collected. From this collection of valid substrings, a greedy algorithm is used to select the maximum number of non-overlapping substrings, ensuring the total length is minimized in case of a tie.

Algorithm

Precompute the first and last occurrence index for each character ('a' through 'z') in the input string s.
Initialize an empty list, validIntervals, to store the start and end indices of all valid substrings.
Use nested loops to iterate through all possible substrings s[i..j].
For each substring, perform a check to see if it's valid. A substring s[i..j] is valid if for every character c it contains, all occurrences of c in the original string s lie within the indices [i, j]. This can be verified using the precomputed first and last arrays.
If a substring is valid, add its corresponding interval [i, j] to the validIntervals list.
After checking all substrings, sort the validIntervals list. The primary sorting key is the end index of the interval in ascending order. The secondary key is the length of the interval (end - start + 1), also in ascending order. This secondary sort helps in finding the solution with the minimum total length.
Apply a greedy algorithm to the sorted list to select the maximum number of non-overlapping intervals. Initialize an empty result list and a variable lastEnd to -1.
Iterate through the sorted intervals. If an interval's start is greater than lastEnd, select this interval, add it to the result, and update lastEnd to the interval's end.
Finally, convert the selected intervals back into substrings from the original string s.

Walkthrough

The first step is to preprocess the string s to find the first and last indices of each character. This is stored in two arrays, first and last, of size 26.

Next, we iterate through all possible start (i) and end (j) indices to define every substring s[i..j]. For each of these O(N^2) substrings, we must verify its validity. The validation process involves checking every character within s[i..j]. For each unique character c in the substring, we look up its global first[c] and last[c] indices. If for any character, first[c] < i or last[c] > j, the substring is invalid because it doesn't contain all occurrences of c. This check can take up to O(N) time for each substring, leading to an overall O(N^3) complexity for finding all valid substrings.

Once we have a list of all valid intervals, the problem transforms into a classic interval scheduling problem. We want to pick the maximum number of non-overlapping intervals. To also satisfy the minimum total length requirement, we sort these intervals primarily by their end points and secondarily by their lengths. A greedy pass over this sorted list allows us to pick the optimal set of intervals.

1import java.util.*;2 3class Solution {4    public List<String> maxNumOfSubstrings(String s) {5        int n = s.length();6        int[] first = new int[26];7        int[] last = new int[26];8        Arrays.fill(first, -1);9 10        for (int i = 0; i < n; i++) {11            int charIndex = s.charAt(i) - 'a';12            if (first[charIndex] == -1) {13                first[charIndex] = i;14            }15            last[charIndex] = i;16        }17 18        List<int[]> validIntervals = new ArrayList<>();19        for (int i = 0; i < n; i++) {20            for (int j = i; j < n; j++) {21                if (isValid(s, i, j, first, last)) {22                    validIntervals.add(new int[]{i, j});23                }24            }25        }26 27        validIntervals.sort((a, b) -> {28            if (a[1] != b[1]) {29                return a[1] - b[1];30            }31            return (a[1] - a[0]) - (b[1] - b[0]);32        });33 34        List<String> result = new ArrayList<>();35        int lastEnd = -1;36        for (int[] interval : validIntervals) {37            if (interval[0] > lastEnd) {38                result.add(s.substring(interval[0], interval[1] + 1));39                lastEnd = interval[1];40            }41        }42 43        return result;44    }45 46    private boolean isValid(String s, int start, int end, int[] first, int[] last) {47        Set<Character> seen = new HashSet<>();48        for (int i = start; i <= end; i++) {49            seen.add(s.charAt(i));50        }51 52        for (char c : seen) {53            int charIndex = c - 'a';54            if (first[charIndex] < start || last[charIndex] > end) {55                return false;56            }57        }58        return true;59    }60}

Complexity

Time

O(N^3), where N is the length of the string. Generating all O(N^2) substrings and validating each in O(N) time results in an O(N^3) complexity.

Space

O(N^2), where N is the length of the string. In the worst-case scenario, we might need to store O(N^2) valid intervals.

Trade-offs

Pros

The logic is straightforward and directly follows from the problem definition.
It is guaranteed to find the correct answer.

Cons

The time complexity of O(N^3) is too high for the given constraints (N up to 10^5), leading to a 'Time Limit Exceeded' error on most platforms.
The space complexity of O(N^2) can be very large, potentially causing memory issues for large N.

This highly efficient approach avoids the costly generation of all valid substrings. It's based on the insight that the optimal solution must be composed of a subset of minimal valid substrings. A minimal valid substring is one that cannot be made smaller without violating the conditions. The algorithm efficiently generates a small set of these minimal candidates (at most 26) and then applies the same greedy selection strategy as the previous approach. This reduces the complexity from polynomial to linear time.

Algorithm

Precompute the first and last occurrence indices for each character in s.
Initialize an empty list, candidateIntervals, to store potential minimal valid substrings.
Iterate through each character c from 'a' to 'z'. If c exists in s:
- Determine the initial range [l, r] as [first[c], last[c]].
- Expand this range. The right boundary r must be extended to include the last occurrences of all characters within the current range [l, r]. This is done by iterating from l to r and repeatedly updating r = max(r, last[s.charAt(k)]) until r stabilizes.
- After finding the fully expanded right boundary r, verify if the interval [l, r] is a minimal valid interval. An interval starting at l is minimal if it doesn't contain any character whose first occurrence is before l. Check this by finding the minimum first index among all characters in s[l..r]. If this minimum is equal to l, the interval is minimal and is added to candidateIntervals.
Sort candidateIntervals by their end points, with length as a tie-breaker.
Apply the greedy selection strategy on the sorted candidateIntervals to find the final set of non-overlapping substrings.
Convert the selected intervals to strings and return them.

Walkthrough

The key to this approach is to efficiently find a small set of candidate substrings that is guaranteed to contain the optimal solution. We can deduce that any valid substring containing a character c must span at least from first[c] to last[c]. This forms the basis for finding minimal valid substrings.

First, we precompute the first and last occurrence arrays in O(N) time.

Then, instead of checking all O(N^2) substrings, we generate candidates on a per-character basis. For each of the 26 lowercase letters, we find its minimal valid interval. Let's say we are considering character c. Its interval must start at l = first[c]. The initial right boundary is r = last[c]. However, other characters inside s[l..r] might have their last occurrences after r. So, we must expand r by scanning through s[l..r] and updating r with the maximum last index found. This expansion continues until r no longer changes.

Once we have a potential interval [l, r], we need to ensure it's a minimal one. A minimal interval starting at l cannot contain a character d where first[d] < l. If it did, the true minimal interval would have to start at first[d] or even earlier. So, we perform a final check: if the minimum first index of all characters in s[l..r] is indeed l, we add [l, r] to our list of candidates. Otherwise, we discard it, as it's part of a larger minimal interval that will be found when we process the character at that minimum first index.

This process yields at most 26 candidate intervals. We then sort these candidates and apply the greedy selection algorithm as before. Since the number of candidates is constant, sorting and selection are very fast.

1import java.util.*;2 3class Solution {4    public List<String> maxNumOfSubstrings(String s) {5        int n = s.length();6        int[] first = new int[26];7        int[] last = new int[26];8        Arrays.fill(first, -1);9 10        for (int i = 0; i < n; i++) {11            int charIndex = s.charAt(i) - 'a';12            if (first[charIndex] == -1) {13                first[charIndex] = i;14            }15            last[charIndex] = i;16        }17 18        List<int[]> candidateIntervals = new ArrayList<>();19        for (int i = 0; i < 26; i++) {20            if (first[i] == -1) continue; // Character not in s21 22            int l = first[i];23            int r = getRightmostBoundary(s, l, first, last);24            25            if (r != -1) {26                candidateIntervals.add(new int[]{l, r});27            }28        }29 30        candidateIntervals.sort((a, b) -> {31            if (a[1] != b[1]) {32                return a[1] - b[1];33            }34            return (a[1] - a[0]) - (b[1] - b[0]);35        });36 37        List<String> result = new ArrayList<>();38        int lastEnd = -1;39        for (int[] interval : candidateIntervals) {40            if (interval[0] > lastEnd) {41                result.add(s.substring(interval[0], interval[1] + 1));42                lastEnd = interval[1];43            }44        }45        return result;46    }47 48    private int getRightmostBoundary(String s, int l, int[] first, int[] last) {49        int r = last[s.charAt(l) - 'a'];50        for (int i = l; i <= r; i++) {51            // If a character inside [l,r] must start before l, this l is not a valid start52            if (first[s.charAt(i) - 'a'] < l) {53                return -1;54            }55            r = Math.max(r, last[s.charAt(i) - 'a']);56        }57        return r;58    }59}

Complexity

Time

O(N), where N is the length of the string. Precomputation takes O(N). Generating candidates involves a loop of 26 (constant), and inside, the work done for each character is proportional to the length of its minimal interval, but the total work across all characters is O(N). Sorting and selection on a constant number of intervals is O(1).

Space

O(1). The `first` and `last` arrays, as well as the `candidateIntervals` list, have sizes that depend on the alphabet size (26), which is a constant.

Trade-offs

Pros

Extremely efficient with O(N) time complexity, which passes the given constraints with ease.
Constant space complexity (O(1)) as it only depends on the alphabet size, not the input size.

Cons

The logic for generating the minimal candidate intervals is more complex and less intuitive than the brute-force approach.

Solutions

Solution

1class Solution {2public3  List<String> maxNumOfSubstrings(String s) {4    Map<Character, int[]> startEndMap = new HashMap<Character, int[]>();5    int length = s.length();6    for (int i = 0; i < length; i++) {7      char c = s.charAt(i);8      int[] startEnd = startEndMap.getOrDefault(c, new int[]{-1, -1});9      if (startEnd[0] < 0)10        startEnd[0] = i;11      startEnd[1] = i;12      startEndMap.put(c, startEnd);13    }14    int[] endIndices = new int[length];15    Arrays.fill(endIndices, -1);16    for (int i = 0; i < length; i++) {17      char c = s.charAt(i);18      int[] startEnd = startEndMap.get(c);19      if (startEnd[0] != i)20        continue;21      boolean flag = true;22      int curEnd = startEnd[1];23      for (int j = i + 1; j < length; j++) {24        if (j > curEnd)25          break;26        char nextC = s.charAt(j);27        int[] nextStartEnd = startEndMap.get(nextC);28        if (nextStartEnd[0] < i) {29          flag = false;30          break;31        }32        curEnd = Math.max(curEnd, nextStartEnd[1]);33      }34      if (flag)35        endIndices[i] = curEnd;36    }37    List<String> list = new ArrayList<String>();38    int curStart = -1, curEnd = -1;39    for (int i = 0; i < length; i++) {40      if (i == curEnd) {41        list.add(s.substring(curStart, curEnd + 1));42        continue;43      }44      int end = endIndices[i];45      if (end < 0)46        continue;47      if (curEnd < i) {48        curStart = i;49        curEnd = end;50      } else if (i > curStart && end < curEnd) {51        curStart = i;52        curEnd = end;53      }54      if (i == curEnd)55        list.add(s.substring(curStart, curEnd + 1));56    }57    return list;58  }59}

1// OJ: https://leetcode.com/problems/maximum-number-of-non-overlapping-substrings/ // Time: O(N) // Space: O(N) class Solution { public: vector < string > maxNumOfSubstrings ( string s ) { int N = s . size (); vector < int > left ( 26 , - 1 ), right ( 26 , - 1 ); // the range of each character for ( int i = 0 ; i < N ; ++ i ) { int c = s [ i ] - 'a' ; if ( left [ c ] == - 1 ) left [ c ] = i ; right [ c ] = i ; } for ( int i = 0 ; i < 26 ; ++ i ) { // An inefficient way of generating the ranges satisfying condition 2. if ( left [ i ] == - 1 ) continue ; for ( int j = left [ i ] + 1 ; j < right [ i ]; ++ j ) { int L = left [ s [ j ] - 'a' ], R = right [ s [ j ] - 'a' ]; if ( L < left [ i ]) j = L ; // rewind left [ i ] = min ( left [ i ], L ); right [ i ] = max ( right [ i ], R ); } } vector < int > dp ( N + 1 ), pick ( N + 1 , - 1 ), len ( N + 1 , N + 1 ); for ( int i = 0 ; i < N ; ++ i ) { len [ i + 1 ] = len [ i ]; pick [ i + 1 ] = pick [ i ]; dp [ i + 1 ] = dp [ i ]; int j = 0 ; for (; j < 26 ; ++ j ) { if ( right [ j ] == i ) break ; } if ( j == 26 || dp [ left [ j ]] + 1 < dp [ i + 1 ]) continue ; if ( dp [ left [ j ]] + 1 > dp [ i + 1 ] || len [ left [ j ]] + right [ j ] - left [ j ] + 1 < len [ i ]) { len [ i + 1 ] = len [ left [ j ]] + right [ j ] - left [ j ] + 1 ; // find a better choice, update the choice. pick [ i + 1 ] = j ; } dp [ i + 1 ] = max ( dp [ i + 1 ], dp [ left [ j ]] + 1 ); } vector < string > ans ; for ( int p = pick [ N ]; p != - 1 ;) { // reconstruct the substrings. int L = left [ p ], R = right [ p ]; ans . push_back ( s . substr ( L , R - L + 1 )); p = pick [ L ]; } return ans ; } };

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 problem