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:
s[i..j] and s[x..y], either j < x or i > y is true.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 <= 105s contains only lowercase English letters.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.
Java
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.
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.
JavaScript
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.
| 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. |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,177 views views
Watch 9 more video solutions →Practice Maximum Number of Non-Overlapping Substrings with our built-in code editor and test cases.
Practice on FleetCode