Maximum Number of Non-Overlapping Substrings - Video Solutions

Problem Overview: Given a string s, return the maximum number of non-overlapping substrings such that if a character appears in a substring, all occurrences of that character in the entire string are contained within that substring. Among all valid answers, choose the set with the smallest total length.

The constraint forces each chosen substring to fully cover the first and last occurrence of every character inside it. The main challenge is identifying valid character ranges and then selecting a set of non-overlapping segments that maximizes the count.

Approach 1: Interval Merging (O(n) time, O(1) space)

Start by computing the first and last occurrence of every character in the string. For each character's starting index, attempt to expand its interval until it contains the full range of every character appearing inside it. This works similarly to interval expansion: scan from the start index to the current right boundary and update the boundary if another character extends further. If the expansion reaches a character whose first occurrence is before the starting index, the interval is invalid and must be skipped.

After generating all valid intervals, select non-overlapping ones while minimizing total length. Sort or process them by their right boundary and merge overlapping segments accordingly. Because the alphabet size is limited (26 lowercase letters), the interval construction and checks remain linear. This approach relies heavily on interval reasoning over characters in a string.

Approach 2: Greedy Segment Selection (O(n) time, O(1) space)

A more direct method builds valid segments and selects them greedily. First compute arrays for the first and last position of each character. For each index that equals the first occurrence of its character, try constructing the minimal valid substring by expanding the right boundary while scanning forward. During expansion, if a character appears whose first occurrence lies before the current start, the segment becomes invalid.

If the segment is valid, compare it with the previously chosen substring. When intervals overlap, prefer the one with the smaller right boundary since it leaves more room for future selections. This greedy rule maximizes the total number of substrings. The algorithm performs a single pass over the string and constant-size character tracking, making it efficient for large inputs. This strategy combines interval reasoning with a greedy selection pattern commonly used in substring segmentation problems.

Recommended for interviews: The greedy segment selection approach is typically expected. It demonstrates that you can derive valid character ranges and apply a greedy rule to maximize non-overlapping intervals. Discussing interval construction first shows clear understanding of the underlying string structure, while the greedy selection proves you can optimize the final result.