Maximum Number of Non-Overlapping Substrings

Description

Maximum Number of Non-Overlapping Substrings

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.

Primary Approach: Range Expansion + Greedy Interval Scheduling ($O(N)$ Time, $O(1)$ Space)

Intuition

To solve 1520. Maximum Number of Non-Overlapping Substrings, we break the problem into two logical phases:

1. Find Valid Intervals:
   A valid substring containing character c must contain all occurrences of c.
   • First, record the first and last occurrence indices for all 26 lowercase English letters.
   • For each character present in s, treat start = first[c] as a potential substring start.
   • Expand the range [start, end] by checking every character within it:
     • If a character inside has first[ch] < start, it means extending to cover ch would push our starting point further left than start. Thus, no valid substring can start at start—mark it invalid and stop expanding.
     • Otherwise, extend end = max(end, last[ch]).
2. Greedy Selection (Activity Selection Problem):
   • Sort all valid candidate intervals [start, end] in ascending order by their end index (end).
   • Iteratively select intervals if start > prevEnd.
   • Why this minimizes length: If one valid interval is nested inside another (e.g., "bb" inside "abba"), the smaller nested interval will finish strictly earlier. Greedily picking intervals with earlier end times maximizes the total count of non-overlapping substrings and automatically chooses smaller substrings over larger enclosing ones.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
class Solution {
    public List<String> maxNumOfSubstrings(String s) {
        int n = s.length();
        int[] first = new int[26];
        int[] last = new int[26];
        Arrays.fill(first, -1);
        Arrays.fill(last, -1);
 
        // Record first and last occurrence of each character
        for (int i = 0; i < n; i++) {
            int ch = s.charAt(i) - 'a';
            if (first[ch] == -1) {
                first[ch] = i;
            }
            last[ch] = i;
        }
 
        List<int[]> validIntervals = new ArrayList<>();
 
        // Generate valid intervals starting at first[i] for each character
        for (int i = 0; i < 26; i++) {
            if (first[i] == -1) continue;
 
            int start = first[i];
            int end = last[i];
            boolean isValid = true;
 
            for (int k = start; k <= end; k++) {
                int ch = s.charAt(k) - 'a';
 
                // If character inside requires an index before 'start', invalid!
                if (first[ch] < start) {
                    isValid = false;
                    break;
                }
                end = Math.max(end, last[ch]);
            }
 
            if (isValid) {
                validIntervals.add(new int[]{start, end});
            }
        }
 
        // Sort valid intervals by end index in ascending order
        validIntervals.sort((a, b) -> Integer.compare(a[1], b[1]));
 
        List<String> result = new ArrayList<>();
        int prevEnd = -1;
 
        // Greedily pick non-overlapping intervals
        for (int[] interval : validIntervals) {
            int start = interval[0];
            int end = interval[1];
 
            if (start > prevEnd) {
                result.add(s.substring(start, end + 1));
                prevEnd = end;
            }
        }
 
        return result;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Recording first/last indices takes $O(N)$. Expanding ranges for at most 26 starting positions takes $O(26\times N)=O(N)$. Sorting at most 26 valid intervals takes $O(26\log 26)=O(1)$. Overall time complexity is linear.
• Space Complexity: $O(1)$ auxiliary space — Fixed size arrays of size 26 for storing character bounds and at most 26 candidate intervals.

---

Key Interview Discussion Points

• Why start expansion only at first[c]?
  Any valid substring containing c must include its first occurrence. Therefore, if a valid substring starts with c, its start index must be first[c].
• Why sorting by end solves minimum length:
  Suppose [s1, e1] and [s2, e2] are both valid intervals where [s2, e2] is strictly inside [s1, e1]. Then $e2<e1$. By sorting by end times, [s2, e2] is selected first, naturally preferring shorter inner substrings over larger outer ones.

---

Easy Memory Rule

“Expand bounds for 26 first[c] starting points $\to$ Discard if first[ch] < start $\to$ Sort valid intervals by end $\to$ Greedily select non-overlapping!”