1520. Maximum Number of Non-Overlapping Substrings

1520. Maximum Number of Non-Overlapping Substrings

Difficulty: Hard

Topics: Senior Staff, Hash Table, String, Greedy, Sorting, Weekly Contest 198

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:

• 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.
• 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.

Example 1:

• 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:

• 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.

Example 3:

• Input: s = "abac"
• Output: ["b","c"]

Example 4:

• Input: s = "abc`"
• Output: ["a","b","c"]

Example 5:

• Input: s = "aaaa"
• Output: ["aaaa"]

Example 6:

• Input: s = "ababa"
• Output: ["ababa"]

Example 7:

• Input: s = "a"
• Output: ["a"]

Constraints:

• 1 <= s.length <= 10⁵
• s contains only lowercase English letters.

Hint:

1. Notice that it's impossible for any two valid substrings to overlap unless one is inside another.
2. We can start by finding the starting and ending index for each character.
3. From these indices, we can form the substrings by expanding each character's range if necessary (if another character exists in the range with smaller/larger starting/ending index).
4. Sort the valid substrings by length and greedily take those with the smallest length, discarding the ones that overlap those we took.

Solution:

We compute the minimal valid interval for each character, expand it until every character inside the interval has all its occurrences included, then greedily select non-overlapping intervals sorted by earliest ending time. Ties are broken by shorter interval length to minimize total length.

Approach

• Store first[c], last[c], and all positions for every lowercase letter.
• For each character c, start with the interval [first[c], last[c]].
• Expand the interval until stable:
  • If any character k appears inside [l, r], merge all occurrences of k into the interval.
  • Update l = min(l, first[k]) and r = max(r, last[k]).
• Keep only intervals whose left endpoint equals first[c]; other expanded intervals are duplicates generated by their actual leftmost character.
• Sort valid intervals by:
  • ending index ascending,
  • starting index descending when endings are equal, which prefers shorter intervals.
• Greedily choose an interval if its start is greater than the end of the last chosen interval.
• Return the chosen substrings using substr.

Let's implement this solution in PHP: 1520. Maximum Number of Non-Overlapping Substrings

`php
<?php
/**

• @param String $s
• @return String[] / function maxNumOfSubstrings(string $s): array { ... ... ... /*
  • go to ./solution.php */ }

// Test cases
echo maxNumOfSubstrings("adefaddaccc") . "\n"; // Output: ["e","f","ccc"]
echo maxNumOfSubstrings("abbaccd") . "\n"; // Output: ["d","bb","cc"]
echo maxNumOfSubstrings("abac") . "\n"; // Output: ["b","c"]
echo maxNumOfSubstrings("abc") . "\n"; // Output: ["a","b","c"]
echo maxNumOfSubstrings("aaaa") . "\n"; // Output: ["aaaa"]
echo maxNumOfSubstrings("ababa") . "\n"; // Output: ["ababa"]
echo maxNumOfSubstrings("a") . "\n"; // Output: ["a"]
?>
`

Explanation:

• A valid substring containing character c must contain all occurrences of c, so its minimum possible span is [first[c], last[c]].
• If that span contains another character k, then validity forces all occurrences of k to be included too. This may expand the interval again.
• Repeating this expansion gives the smallest valid substring that can start at first[c].
• The check l === first[c] avoids adding the same expanded interval multiple times.
• Valid intervals cannot partially overlap; they are either disjoint or nested. Therefore, greedy earliest-finish selection gives the maximum number of non-overlapping substrings.
• For equal ending points, choosing the later starting point gives a shorter substring and does not hurt future choices.
• lastEnd tracks the end of the last chosen substring, ensuring no overlap.

Complexity Analysis

• Let n = strlen(s) and alphabet size Σ = 26.
• Preprocessing: O(n).
• Expansion for each character: at most O(Σ^3 log n), which is effectively constant since Σ = 26.
• Sorting at most 26 intervals: O(Σ log Σ).
• Overall time: O(n + Σ^3 log n), practically O(n).
• Space: O(n) for storing character positions, plus O(Σ) extra.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub