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:

  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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

1
2
3

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^5
  • s contains 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

  1. For each character, record its first and last occurrence in the string.
  2. For each character, expand its interval to cover all characters inside its current interval.
  3. Collect all such intervals and sort them by their end index.
  4. Greedily select non-overlapping intervals with the smallest end index.
  5. Return the selected substrings.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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), where n is the length of s, since each character and interval is processed a constant number of times.
  • 🧺 Space complexity: O(n), for storing intervals and the answer.