# Maximum Number of Non-Overlapping Substrings **Difficulty:** HARD [External](https://leetcode.com/problems/maximum-number-of-non-overlapping-substrings) Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-non-overlapping-substrings **Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy) **Data structures:** String --- ## Problem 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: 1. 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. 2. 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 <= 105` * `s` contains only lowercase English letters. # Approaches ## Generate All Valid Substrings and Greedy Selection 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. **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. **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. ### Explanation 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. ```java import java.util.*; class Solution { public List maxNumOfSubstrings(String s) { int n = s.length(); int[] first = new int[26]; int[] last = new int[26]; Arrays.fill(first, -1); for (int i = 0; i < n; i++) { int charIndex = s.charAt(i) - 'a'; if (first[charIndex] == -1) { first[charIndex] = i; } last[charIndex] = i; } List validIntervals = new ArrayList<>(); for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { if (isValid(s, i, j, first, last)) { validIntervals.add(new int[]{i, j}); } } } validIntervals.sort((a, b) -> { if (a[1] != b[1]) { return a[1] - b[1]; } return (a[1] - a[0]) - (b[1] - b[0]); }); List result = new ArrayList<>(); int lastEnd = -1; for (int[] interval : validIntervals) { if (interval[0] > lastEnd) { result.add(s.substring(interval[0], interval[1] + 1)); lastEnd = interval[1]; } } return result; } private boolean isValid(String s, int start, int end, int[] first, int[] last) { Set seen = new HashSet<>(); for (int i = start; i <= end; i++) { seen.add(s.charAt(i)); } for (char c : seen) { int charIndex = c - 'a'; if (first[charIndex] < start || last[charIndex] > end) { return false; } } return true; } } ``` ### 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`. ## Greedy Approach with Optimized Candidate Generation 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. **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. **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. ### Explanation 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. ```java import java.util.*; class Solution { public List maxNumOfSubstrings(String s) { int n = s.length(); int[] first = new int[26]; int[] last = new int[26]; Arrays.fill(first, -1); for (int i = 0; i < n; i++) { int charIndex = s.charAt(i) - 'a'; if (first[charIndex] == -1) { first[charIndex] = i; } last[charIndex] = i; } List candidateIntervals = new ArrayList<>(); for (int i = 0; i < 26; i++) { if (first[i] == -1) continue; // Character not in s int l = first[i]; int r = getRightmostBoundary(s, l, first, last); if (r != -1) { candidateIntervals.add(new int[]{l, r}); } } candidateIntervals.sort((a, b) -> { if (a[1] != b[1]) { return a[1] - b[1]; } return (a[1] - a[0]) - (b[1] - b[0]); }); List result = new ArrayList<>(); int lastEnd = -1; for (int[] interval : candidateIntervals) { if (interval[0] > lastEnd) { result.add(s.substring(interval[0], interval[1] + 1)); lastEnd = interval[1]; } } return result; } private int getRightmostBoundary(String s, int l, int[] first, int[] last) { int r = last[s.charAt(l) - 'a']; for (int i = l; i <= r; i++) { // If a character inside [l,r] must start before l, this l is not a valid start if (first[s.charAt(i) - 'a'] < l) { return -1; } r = Math.max(r, last[s.charAt(i) - 'a']); } return r; } } ``` ### 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. # Solutions ### Java ```java class Solution { public List maxNumOfSubstrings(String s) { Map startEndMap = new HashMap(); int length = s.length(); for (int i = 0; i < length; i++) { char c = s.charAt(i); int[] startEnd = startEndMap.getOrDefault(c, new int[]{-1, -1}); if (startEnd[0] < 0) startEnd[0] = i; startEnd[1] = i; startEndMap.put(c, startEnd); } int[] endIndices = new int[length]; Arrays.fill(endIndices, -1); for (int i = 0; i < length; i++) { char c = s.charAt(i); int[] startEnd = startEndMap.get(c); if (startEnd[0] != i) continue; boolean flag = true; int curEnd = startEnd[1]; for (int j = i + 1; j < length; j++) { if (j > curEnd) break; char nextC = s.charAt(j); int[] nextStartEnd = startEndMap.get(nextC); if (nextStartEnd[0] < i) { flag = false; break; } curEnd = Math.max(curEnd, nextStartEnd[1]); } if (flag) endIndices[i] = curEnd; } List list = new ArrayList(); int curStart = -1, curEnd = -1; for (int i = 0; i < length; i++) { if (i == curEnd) { list.add(s.substring(curStart, curEnd + 1)); continue; } int end = endIndices[i]; if (end < 0) continue; if (curEnd < i) { curStart = i; curEnd = end; } else if (i > curStart && end < curEnd) { curStart = i; curEnd = end; } if (i == curEnd) list.add(s.substring(curStart, curEnd + 1)); } return list; } } ``` ### CPP ```cpp // 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 ; } }; ```