Maximum Number of Non-Overlapping Substrings
HardUpdated: Aug 2, 2025
Practice on:
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:
- 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.
Examples
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 <= 10^5scontains only lowercase English letters.
Solution
Method 1 – Greedy + Interval Merging
Intuition
For each character, find the leftmost and rightmost occurrence. For each character, expand its interval to include all characters inside it. Then, greedily select the smallest non-overlapping intervals.
Approach
- For each character, record its first and last occurrence in the string.
- For each character, expand its interval to cover all characters inside its current interval.
- Collect all such intervals and sort them by their end index.
- Greedily select non-overlapping intervals with the smallest end index.
- Return the selected substrings.
Code
C++
class Solution {
public:
vector<string> maxNumOfSubstrings(string s) {
int n = s.size();
vector<int> l(26, n), r(26, -1);
for (int i = 0; i < n; ++i) {
l[s[i]-'a'] = min(l[s[i]-'a'], i);
r[s[i]-'a'] = max(r[s[i]-'a'], i);
}
vector<pair<int, int>> intervals;
for (int c = 0; c < 26; ++c) {
if (l[c] > r[c]) continue;
int left = l[c], right = r[c], changed = 1;
while (changed) {
changed = 0;
for (int i = left; i <= right; ++i) {
int cc = s[i] - 'a';
if (l[cc] < left) { left = l[cc]; changed = 1; }
if (r[cc] > right) { right = r[cc]; changed = 1; }
}
}
if (left == l[c]) intervals.emplace_back(right, left);
}
sort(intervals.begin(), intervals.end());
vector<string> ans;
int last = -1;
for (auto& [r, l] : intervals) {
if (l > last) {
ans.push_back(s.substr(l, r-l+1));
last = r;
}
}
return ans;
}
};
Go
func maxNumOfSubstrings(s string) []string {
n := len(s)
l, r := make([]int, 26), make([]int, 26)
for i := range l { l[i] = n; r[i] = -1 }
for i, ch := range s {
idx := int(ch - 'a')
if i < l[idx] { l[idx] = i }
if i > r[idx] { r[idx] = i }
}
type pair struct{ r, l int }
intervals := []pair{}
for c := 0; c < 26; c++ {
if l[c] > r[c] { continue }
left, right, changed := l[c], r[c], true
for changed {
changed = false
for i := left; i <= right; i++ {
cc := int(s[i] - 'a')
if l[cc] < left { left = l[cc]; changed = true }
if r[cc] > right { right = r[cc]; changed = true }
}
}
if left == l[c] {
intervals = append(intervals, pair{r: right, l: left})
}
}
sort.Slice(intervals, func(i, j int) bool { return intervals[i].r < intervals[j].r })
ans := []string{}
last := -1
for _, p := range intervals {
if p.l > last {
ans = append(ans, s[p.l:p.r+1])
last = p.r
}
}
return ans
}
Java
import java.util.*;
class Solution {
public List<String> maxNumOfSubstrings(String s) {
int n = s.length();
int[] l = new int[26], r = new int[26];
Arrays.fill(l, n); Arrays.fill(r, -1);
for (int i = 0; i < n; i++) {
int idx = s.charAt(i) - 'a';
l[idx] = Math.min(l[idx], i);
r[idx] = Math.max(r[idx], i);
}
List<int[]> intervals = new ArrayList<>();
for (int c = 0; c < 26; c++) {
if (l[c] > r[c]) continue;
int left = l[c], right = r[c];
boolean changed = true;
while (changed) {
changed = false;
for (int i = left; i <= right; i++) {
int cc = s.charAt(i) - 'a';
if (l[cc] < left) { left = l[cc]; changed = true; }
if (r[cc] > right) { right = r[cc]; changed = true; }
}
}
if (left == l[c]) intervals.add(new int[]{right, left});
}
intervals.sort(Comparator.comparingInt(a -> a[0]));
List<String> ans = new ArrayList<>();
int last = -1;
for (int[] p : intervals) {
if (p[1] > last) {
ans.add(s.substring(p[1], p[0]+1));
last = p[0];
}
}
return ans;
}
}
Kotlin
class Solution {
fun maxNumOfSubstrings(s: String): List<String> {
val n = s.length
val l = IntArray(26) { n }
val r = IntArray(26) { -1 }
for (i in s.indices) {
val idx = s[i] - 'a'
l[idx] = minOf(l[idx], i)
r[idx] = maxOf(r[idx], i)
}
val intervals = mutableListOf<Pair<Int, Int>>()
for (c in 0 until 26) {
if (l[c] > r[c]) continue
var left = l[c]
var right = r[c]
var changed = true
while (changed) {
changed = false
for (i in left..right) {
val cc = s[i] - 'a'
if (l[cc] < left) { left = l[cc]; changed = true }
if (r[cc] > right) { right = r[cc]; changed = true }
}
}
if (left == l[c]) intervals.add(Pair(right, left))
}
intervals.sortBy { it.first }
val ans = mutableListOf<String>()
var last = -1
for ((r, l) in intervals) {
if (l > last) {
ans.add(s.substring(l, r+1))
last = r
}
}
return ans
}
}
Python
class Solution:
def maxNumOfSubstrings(self, s: str) -> list[str]:
n = len(s)
l = [n] * 26
r = [-1] * 26
for i, ch in enumerate(s):
idx = ord(ch) - ord('a')
l[idx] = min(l[idx], i)
r[idx] = max(r[idx], i)
intervals = []
for c in range(26):
if l[c] > r[c]: continue
left, right = l[c], r[c]
changed = True
while changed:
changed = False
for i in range(left, right+1):
cc = ord(s[i]) - ord('a')
if l[cc] < left:
left = l[cc]
changed = True
if r[cc] > right:
right = r[cc]
changed = True
if left == l[c]:
intervals.append((right, left))
intervals.sort()
ans = []
last = -1
for r, lft in intervals:
if lft > last:
ans.append(s[lft:r+1])
last = r
return ans
Rust
impl Solution {
pub fn max_num_of_substrings(s: String) -> Vec<String> {
let n = s.len();
let s = s.as_bytes();
let mut l = vec![n; 26];
let mut r = vec![-1; 26];
for (i, &ch) in s.iter().enumerate() {
let idx = (ch - b'a') as usize;
l[idx] = l[idx].min(i);
r[idx] = r[idx].max(i as i32);
}
let mut intervals = vec![];
for c in 0..26 {
if l[c] as i32 > r[c] { continue; }
let (mut left, mut right) = (l[c], r[c] as usize);
let mut changed = true;
while changed {
changed = false;
for i in left..=right {
let cc = (s[i] - b'a') as usize;
if l[cc] < left { left = l[cc]; changed = true; }
if r[cc] as usize > right { right = r[cc] as usize; changed = true }
}
}
if left == l[c] {
intervals.push((right, left));
}
}
intervals.sort();
let mut ans = vec![];
let mut last = -1;
for (r, l) in intervals {
if l as i32 > last {
ans.push(String::from_utf8(s[l..=r].to_vec()).unwrap());
last = r as i32;
}
}
ans
}
}
TypeScript
class Solution {
maxNumOfSubstrings(s: string): string[] {
const n = s.length;
const l = Array(26).fill(n);
const r = Array(26).fill(-1);
for (let i = 0; i < n; i++) {
const idx = s.charCodeAt(i) - 97;
l[idx] = Math.min(l[idx], i);
r[idx] = Math.max(r[idx], i);
}
const intervals: [number, number][] = [];
for (let c = 0; c < 26; c++) {
if (l[c] > r[c]) continue;
let left = l[c], right = r[c], changed = true;
while (changed) {
changed = false;
for (let i = left; i <= right; i++) {
const cc = s.charCodeAt(i) - 97;
if (l[cc] < left) { left = l[cc]; changed = true; }
if (r[cc] > right) { right = r[cc]; changed = true; }
}
}
if (left === l[c]) intervals.push([right, left]);
}
intervals.sort((a, b) => a[0] - b[0]);
const ans: string[] = [];
let last = -1;
for (const [r, lft] of intervals) {
if (lft > last) {
ans.push(s.slice(lft, r+1));
last = r;
}
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n), wherenis the length ofs, since each character and interval is processed a constant number of times. - 🧺 Space complexity:
O(n), for storing intervals and the answer.