Maximum Number of Non-Overlapping Substrings

Maximum Number of Non-Overlapping Substrings is a sneaky greedy problem. The hard part is not the greedy pick at the end — it is realizing that each character forces a minimal valid interval, and that once you have those intervals the problem collapses into a familiar "pick the most non-overlapping intervals" exercise.

The slow way first

You might try every possible substring s[lo:hi+1], check whether it is valid, then search for the best non-overlapping combination. There are O(n²) substrings and checking validity is O(n) each, and the combination search explodes. Far too slow.

The question to ask: for a given character, what is the smallest valid substring that even contains it? If we can compute that one interval per character cheaply, we never need to consider arbitrary substrings at all.

The idea: one minimal interval per character

Each character c has a first and last occurrence. Its smallest interval must at least span [first[c], last[c]]. But that window may contain another character d whose own occurrences leak outside the window — so we expand the right end to swallow d, and keep scanning. If while expanding we ever find a character whose first occurrence sits before our left end, this interval can never be valid, so we drop it.

Once every character has produced (at most) one valid interval, sort by right endpoint and greedily keep an interval whenever it starts after the previously kept interval's end. That is the classic interval-scheduling greedy, which maximizes the count, and because each interval is already minimal it also minimizes total length.

Walk through it

Step through the animation on 'abab'. We start with a, which spans indices 0 to 2. But index 1 holds a b, and b also lives at index 3 — outside the window — so the window expands its right end to 3. Now [0, 3] holds every a and every b, so it is valid. b produces the same window. After sorting, only [0, 3] survives the greedy scan, giving one substring.

Pseudocode

record first[c] and last[c] for every character c
define grow(lo):
    hi = last[s[lo]]
    i = lo
    while i <= hi:
        if first[s[i]] < lo:   # a char leaks left -> invalid
            return nothing
        hi = max(hi, last[s[i]])   # expand to contain this char
        i += 1
    return interval (lo, hi)
build a valid interval for each distinct character
sort the valid intervals by right endpoint
prev = -1
for each interval (lo, hi):
    if lo > prev:        # non-overlapping -> keep it
        take s[lo:hi+1]
        prev = hi
return the kept substrings

The Python solution

def max_substrings(s):
    first = {c: s.index(c) for c in set(s)}
    last = {c: s.rindex(c) for c in set(s)}
    def grow(lo):
        hi = last[s[lo]]
        i = lo
        while i <= hi:
            if first[s[i]] < lo:
                return None
            hi = max(hi, last[s[i]])
            i += 1
        return (lo, hi)
    spans = sorted(filter(None, (grow(first[c]) for c in set(s))), key=lambda p: p[1])
    res, prev = [], -1
    for lo, hi in spans:
        if lo > prev:
            res.append(s[lo:hi + 1]); prev = hi
    return res

• first and last map each character to its first and last index — the seed of every interval.
• grow(lo) starts the window at last[s[lo]] and walks rightward, expanding hi to contain any character it meets.
• The first[s[i]] < lo check aborts an interval that can never be valid: a character inside it also appears to the left of lo.
• We start each character at first[c] so the window genuinely begins at its earliest occurrence.
• spans is the list of valid intervals, sorted by right endpoint — the key to the greedy pick.
• The final loop keeps an interval only when lo > prev, guaranteeing non-overlap while maximizing the count.

Complexity

With only 26 possible characters the whole thing is effectively linear in the string length. The space is O(1) because the maps hold at most 26 entries.

When this pattern shows up

Practice