Maximum Number of Non-Overlapping Substrings

hard string greedy intervals

Problem

Given a lowercase string s, find the maximum number of non-empty substrings that (1) do not overlap and (2) whenever a substring contains a character c, it must contain every occurrence of c in s. Among solutions with the same count, return the one with minimum total length. The substrings may be returned in any order.

Inputs = "adefaddaccc"

Output["e", "f", "ccc"]

"e" and "f" each appear once, and "ccc" holds all three c's. Picking "adefadda" + "ccc" gives only 2; splitting the front into "e" and "f" yields 3 substrings.

s (lowercase letters)

def maxNumOfSubstrings(s):
    first, last = {}, {}
    for i, ch in enumerate(s):          # record first/last index per char
        if ch not in first:
            first[ch] = i
        last[ch] = i

    def expand(ch):                     # smallest valid window anchored at first[ch]
        l, r = first[ch], last[ch]
        i = l
        while i <= r:
            c = s[i]
            if first[c] < l:            # a char reaches left of anchor -> invalid
                return None
            if last[c] > r:            # pull the right edge out to cover all of c
                r = last[c]
            i += 1
        return (l, r)

    intervals = []
    for ch in set(s):                   # one candidate window per distinct char
        w = expand(ch)
        if w is not None:
            intervals.append(w)

    intervals.sort(key=lambda w: w[1])  # greedy by earliest right end
    res, prev_end = [], -1
    for l, r in intervals:
        if l > prev_end:                # disjoint from the last chosen window
            res.append(s[l:r + 1])
            prev_end = r
    return res

function maxNumOfSubstrings(s) {
  const first = {}, last = {};
  for (let i = 0; i < s.length; i++) {     // first/last index per char
    if (!(s[i] in first)) first[s[i]] = i;
    last[s[i]] = i;
  }
  function expand(ch) {                     // smallest valid window for ch
    let l = first[ch], r = last[ch];
    for (let i = l; i <= r; i++) {
      const c = s[i];
      if (first[c] < l) return null;        // reaches left of anchor -> invalid
      if (last[c] > r) r = last[c];         // extend right to cover all of c
    }
    return [l, r];
  }
  const intervals = [];
  for (const ch of new Set(s)) {            // one candidate per distinct char
    const w = expand(ch);
    if (w) intervals.push(w);
  }
  intervals.sort((a, b) => a[1] - b[1]);    // greedy by earliest right end
  const res = []; let prevEnd = -1;
  for (const [l, r] of intervals) {
    if (l > prevEnd) {                       // disjoint from last chosen
      res.push(s.slice(l, r + 1));
      prevEnd = r;
    }
  }
  return res;
}

List<String> maxNumOfSubstrings(String s) {
    int[] first = new int[26], last = new int[26];
    Arrays.fill(first, -1);
    for (int i = 0; i < s.length(); i++) {       // first/last index per char
        int c = s.charAt(i) - 'a';
        if (first[c] == -1) first[c] = i;
        last[c] = i;
    }
    List<int[]> intervals = new ArrayList<>();
    for (int ch = 0; ch < 26; ch++) {            // one candidate per distinct char
        if (first[ch] == -1) continue;
        int l = first[ch], r = last[ch], i = l;
        boolean ok = true;
        while (i <= r) {                          // expand to smallest valid window
            int c = s.charAt(i) - 'a';
            if (first[c] < l) { ok = false; break; }
            if (last[c] > r) r = last[c];
            i++;
        }
        if (ok) intervals.add(new int[]{l, r});
    }
    intervals.sort((a, b) -> a[1] - b[1]);       // greedy by earliest right end
    List<String> res = new ArrayList<>();
    int prevEnd = -1;
    for (int[] w : intervals) {
        if (w[0] > prevEnd) {                     // disjoint from last chosen
            res.add(s.substring(w[0], w[1] + 1));
            prevEnd = w[1];
        }
    }
    return res;
}

vector<string> maxNumOfSubstrings(string s) {
    vector<int> first(26, -1), last(26, -1);
    for (int i = 0; i < (int)s.size(); i++) {    // first/last index per char
        int c = s[i] - 'a';
        if (first[c] == -1) first[c] = i;
        last[c] = i;
    }
    vector<pair<int,int>> intervals;
    for (int ch = 0; ch < 26; ch++) {            // one candidate per distinct char
        if (first[ch] == -1) continue;
        int l = first[ch], r = last[ch], i = l;
        bool ok = true;
        while (i <= r) {                          // expand to smallest valid window
            int c = s[i] - 'a';
            if (first[c] < l) { ok = false; break; }
            if (last[c] > r) r = last[c];
            i++;
        }
        if (ok) intervals.push_back({l, r});
    }
    sort(intervals.begin(), intervals.end(),     // greedy by earliest right end
         [](auto& a, auto& b){ return a.second < b.second; });
    vector<string> res;
    int prevEnd = -1;
    for (auto& w : intervals) {
        if (w.first > prevEnd) {                  // disjoint from last chosen
            res.push_back(s.substr(w.first, w.second - w.first + 1));
            prevEnd = w.second;
        }
    }
    return res;
}

Explanation

Rule 2 — a substring must contain all occurrences of any character it holds — forces a tight structure: any valid substring is completely determined by where it starts. So we only ever need to consider one candidate window per distinct character, anchored at that character's first occurrence.

First we record first[c] and last[c] for every letter. For a character ch, its window must at least span [first[ch], last[ch]]. We then walk that range: every character c we meet inside must have all its occurrences inside too. If last[c] lies past the current right edge, we push the right edge out to last[c] and keep scanning. If first[c] lies before our left anchor, the window can never be valid starting here, so we discard this candidate.

This expansion gives the smallest valid substring that begins at each anchor. A key fact: two valid windows can never partially overlap — one is fully inside the other, or they are disjoint. That turns the final choice into a classic interval-scheduling problem.

To maximize the count we sort the candidate windows by their right end and greedily take a window whenever its left edge starts strictly after the right end of the last one we took. Because every candidate is already the minimal window for its anchor, this same greedy automatically yields the minimum total length.

For "adefaddaccc" the candidate windows are "e", "f", "adefadda", and "ccc". Sorted by right end, the greedy keeps "e", then "f", then "ccc" (it skips "adefadda" because it overlaps "e"), giving 3 substrings.

Time: O(n · 26) Space: O(26)