1520. Maximum Number of Non-Overlapping Substrings

Problem Overview

A valid substring must include every occurrence of each letter it contains.

Intuition

A valid substring must include every occurrence of each letter it contains. Longer valid ranges that wrap shorter ones never help the count, so take the shortest valid pieces greedily from left to right and replace a previous piece whenever a later valid interval nests inside it.

Algorithm

1Record the first and last index of each letter in one pass.
2At each index that is a letter first occurrence, expand right until every letter inside is fully covered.
3If any letter in that range starts before the candidate left, reject the candidate.
4If the candidate starts after the previous chosen interval, append it; otherwise replace the previous interval with this shorter nested one.
5Materialize the chosen intervals as substrings at the end.

Example Walkthrough

Input: s = "adefaddaccc"

1.Letter ranges force some large candidates that nest smaller valid pieces.
2.Greedy replacement keeps compact pieces such as "e", "f", and "ccc".
3.Those intervals do not overlap and maximize the count.

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

Common Pitfalls

•Only start expansion at a letter first occurrence; later starts are redundant.
•Expanding right may grow as new letters appear; keep updating the end bound.
•Prefer nested shorter intervals over earlier longer ones to maximize count and minimize total length.
•There are at most 26 candidate starts, so the scan stays linear.

1520.cs

// Approach: For each letter record first/last index. At each first occurrence,
// expand the candidate [i, right] until every letter inside is fully covered;
// reject if any letter starts before i. Process left to right: append a new
// interval when disjoint; otherwise replace the previous one with the later
// nested shorter interval (maximizes count, then minimizes total length).
// Complexity: O(n) time (at most 26 expansions), O(1) extra beyond the answer.
public class Solution
{
    public IList<string> MaxNumOfSubstrings(string s)
    {
        int n = s.Length;
        int[] leftmost = new int[26];
        int[] rightmost = new int[26];
        Array.Fill(leftmost, n);
        Array.Fill(rightmost, -1);

        for (int i = 0; i < n; i++)
        {
            int c = s[i] - 'a';
            leftmost[c] = Math.Min(leftmost[c], i);
            rightmost[c] = i;
        }

        List<(int L, int R)> intervals = new();
        int lastR = -1;

        for (int i = 0; i < n; i++)
        {
            if (i != leftmost[s[i] - 'a'])
                continue;

            int newR = ExpandRight(s, i, leftmost, rightmost);
            if (newR < 0)
                continue;

            if (i <= lastR && intervals.Count > 0)
                intervals[intervals.Count - 1] = (i, newR);
            else
                intervals.Add((i, newR));

            lastR = newR;
        }

        List<string> ans = new(intervals.Count);
        foreach (var (L, R) in intervals)
            ans.Add(s.Substring(L, R - L + 1));
        return ans;
    }

    // Expand from first occurrence i; return inclusive right end or -1 if invalid.
    private static int ExpandRight(string s, int i, int[] leftmost, int[] rightmost)
    {
        int right = rightmost[s[i] - 'a'];
        for (int j = i; j <= right; j++)
        {
            if (leftmost[s[j] - 'a'] < i)
                return -1;
            right = Math.Max(right, rightmost[s[j] - 'a']);
        }
        return right;
    }
}

Was this solution helpful?