1520. Maximum Number of Non-Overlapping Substrings

String
Greedy

TIME

O(26 * n)

SPACE

O(1) beyond the output

Intuition

Condition 2 says a chosen substring is closed under "if you contain one c, you contain every c". For a given character c, the shortest closed substring that starts at first[c] is forced: start at first[c], and every character x you encounter while scanning pushes the right end out to at least last[x]. If some x inside has first[x] < first[c], the substring cannot be closed without extending left past first[c], so no valid substring starts there.

Two closed substrings can never partially overlap. If they shared a character, each would have to contain all occurrences of it, and then each would have to contain the other's whole extent. So the candidate intervals form a laminar family: any two are either disjoint or nested. In that setting, the standard interval-scheduling greedy (sort by right end, take an interval whenever it starts after the last taken one) maximises the count and, since nested intervals appear inner-first, also minimises total length.

Approach

Record first[c] and last[c] for all 26 letters.
For each letter c present, build the candidate starting at left = first[c]: set right = last[c], scan i from left to right (extending right to max(right, last[s[i]]) as you go), and abort if first[s[i]] < left. If the scan finishes, keep [left, right].
Sort the kept intervals by right. Walk them, appending each interval whose left is beyond the previous right.
Return the corresponding substrings.

Only a valid interval that is minimal for its start position is ever produced, and the greedy by right end picks the innermost available one from each nested chain, which gives the unique minimum-length answer.

Complexity

Time: O(26 * n), each of at most 26 candidates scans up to the whole string
Space: O(1) beyond the output (26 intervals)

Edge Cases

Single character "a" → ["a"]
All the same letter "aaaa" → one substring, the whole string
All distinct letters → every single character is its own substring, answer has n entries
A character whose span contains a character that also appears before it ("abab" for b) → candidate for b is dropped; the answer is the whole string
Nested spans like "abba" → bb wins over abba because the greedy prefers the earlier right end
Output order does not matter, but the solution emits them left to right

Code

from typing import List


class Solution:
    def maxNumOfSubstrings(self, s: str) -> List[str]:
        """
        1520. Maximum Number of Non-Overlapping Substrings
        Time: O(26 * n)
        Space: O(1) beyond the output
        """
        n = len(s)
        first = {}
        last = {}
        for i, ch in enumerate(s):
            if ch not in first:
                first[ch] = i
            last[ch] = i

        # one closed candidate per letter, starting at that letter's first
        # occurrence; dropped if some inner letter forces extension to the left
        candidates = []
        for ch in first:
            left = first[ch]
            right = last[ch]
            i = left
            valid = True
            while i <= right:
                x = s[i]
                if first[x] < left:
                    valid = False
                    break
                if last[x] > right:
                    right = last[x]
                i += 1
            if valid:
                candidates.append((right, left))

        # candidates are nested or disjoint, so earliest-end greedy picks the
        # most intervals and the innermost ones
        candidates.sort()
        result = []
        prev_end = -1
        for right, left in candidates:
            if left > prev_end:
                result.append(s[left:right + 1])
                prev_end = right
        return result

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 1520. Maximum Number of Non-Overlapping Substrings
 * Time: O(26 * n)
 * Space: O(1) beyond the output
 */
class Solution {
    public List<String> maxNumOfSubstrings(String s) {
        int n = s.length();
        int[] first = new int[26];
        int[] last = new int[26];
        Arrays.fill(first, -1);
        for (int i = 0; i < n; i++) {
            int c = s.charAt(i) - 'a';
            if (first[c] == -1) {
                first[c] = i;
            }
            last[c] = i;
        }

        // one closed candidate per letter, starting at that letter's first
        // occurrence; dropped if some inner letter forces extension to the left
        List<int[]> candidates = new ArrayList<>();
        for (int c = 0; c < 26; c++) {
            if (first[c] == -1) {
                continue;
            }
            int left = first[c];
            int right = last[c];
            boolean valid = true;
            for (int i = left; i <= right; i++) {
                int x = s.charAt(i) - 'a';
                if (first[x] < left) {
                    valid = false;
                    break;
                }
                right = Math.max(right, last[x]);
            }
            if (valid) {
                candidates.add(new int[]{left, right});
            }
        }

        // candidates are nested or disjoint, so earliest-end greedy picks the
        // most intervals and the innermost ones
        candidates.sort((a, b) -> Integer.compare(a[1], b[1]));
        List<String> result = new ArrayList<>();
        int prevEnd = -1;
        for (int[] iv : candidates) {
            if (iv[0] > prevEnd) {
                result.add(s.substring(iv[0], iv[1] + 1));
                prevEnd = iv[1];
            }
        }
        return result;
    }
}