Maximum Number of Non-Overlapping Substrings - Solution & Explanation
Problem Statement
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]ands[x..y], eitherj < xori > yis true. - A substring that contains a certain character
cmust also contain all occurrences ofc.
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 <= 105scontains only lowercase English letters.
Approach Overview
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.
Approach 1: Interval Merging
In this approach, we first collect the first and last occurrence of each character in the string. Using this data, we create intervals, and then merge them to find non-overlapping intervals that contain all occurrences of every character within those intervals. Finally, we select the smallest non-overlapping intervals to ensure maximum substrings with minimum length are chosen.
We first build dictionaries to store the first and last position of each character. Then, we create non-overlapping intervals by scanning through each start of a potential substring and finding its end such that all characters' occurrences are included between the indices. These intervals are sorted and processed to get the maximum that are non-overlapping.
Complexity
Time Complexity: O(n), where n is the length of the string as we traverse the string a constant number of times. Space Complexity: O(1), aside from the result array, as the character count is constant with respect to the input size due to the alphabet limited to lowercase English letters.
Approach 2: Greedy Segment Selection
This greedy approach involves finding intervals for each character based on their first and last appearance, collecting minimum range intervals that fulfill all character occurrence criteria, and then sorting by ends. The intervals are picked so they are non-overlapping and minimal in length, resulting in maximum substring count with minimum overlapping checks.
In the C implementation, arrays are used to monitor first and last occurrences of each character. Intervals are created and sorted via `qsort`, then selected by their availability to ensure no overlap according to made selections. It optimizes using a greedy method to choose minimum-length, valid substrings.
Code
C
JavaScript
Complexity
Time Complexity: O(n log n) due to sorting, where n is the length of the string. Space Complexity: O(n) primarily for interval storage and results.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Interval Merging | Time Complexity: O(n), where n is the length of the string as we traverse the string a constant number of times. Space Complexity: O(1), aside from the result array, as the character count is constant with respect to the input size due to the alphabet limited to lowercase English letters. |
| Greedy Segment Selection | Time Complexity: O(n log n) due to sorting, where n is the length of the string. Space Complexity: O(n) primarily for interval storage and results. |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Interval Merging | O(n) | O(1) | When you want to explicitly construct all valid character intervals and reason about overlapping ranges. |
| Greedy Segment Selection | O(n) | O(1) | Best general solution. Efficient single-pass greedy choice that maximizes substring count. |
Video Solution
Maximum Number of Non-Overlapping Substrings | LeetCode 1520 | Coders Camp • Coders Camp • 7,510 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Number of Non-Overlapping Substrings easy or hard?
Maximum Number of Non-Overlapping Substrings Python/Java solution
How to solve Maximum Number of Non-Overlapping Substrings in O(n)?
What is the best approach for Maximum Number of Non-Overlapping Substrings?
Is Maximum Number of Non-Overlapping Substrings asked at Google/Amazon/Meta?
What data structure is used in Maximum Number of Non-Overlapping Substrings?
What is the time complexity of Maximum Number of Non-Overlapping Substrings?
Ready to solve this problem?
Practice Maximum Number of Non-Overlapping Substrings with our built-in code editor and test cases.
Practice on FleetCode