We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Non-Overlapping Substrings

Number: 1644

Difficulty: Hard

Paid? No

Companies: Amazon

Problem Description

Given a string s of lowercase letters, find the maximum number of non-empty substrings that satisfy the following conditions:

  1. The selected substrings do not overlap.
  2. For any selected substring, if it contains a character c, then the substring must include every occurrence of c in s.

If multiple solutions yield the same number of substrings, return the one with the minimum total length. It is guaranteed that the solution with minimal total length is unique.

Key Insights

  • Precompute the first and last indices of each character in the string.
  • For each character based on its first occurrence, attempt to form the smallest valid substring that covers all its occurrences. During this expansion, if any character within the current candidate has a first occurrence outside the candidate’s range, the candidate is invalid.
  • After collecting all valid intervals (candidate substrings), sort them by their ending indices.
  • Use a greedy selection strategy: choose the substring that ends the earliest and then skip all substrings that overlap with it.

Space and Time Complexity

Time Complexity: O(n) – primarily from scanning the string and processing a constant number (26) of characters. Space Complexity: O(n) – space for storing occurrence indices and intervals.

Solution

We begin by determining the first and last occurrence for every character in s. For each character (considering only its first occurrence), expand its interval to include all characters within and check if the interval is still valid (i.e., for every character within, its first occurrence is not before the interval start). Collect all valid intervals. Finally, sort the intervals by ending index and greedily choose non-overlapping intervals to arrive at the answer.

Code Solutions

# Python solution for Maximum Number of Non-Overlapping Substrings

def maxNumOfSubstrings(s: str):
    # Step 1: Precompute first and last indices for every character
    first, last = {}, {}
    for i, char in enumerate(s):
        if char not in first:
            first[char] = i
        last[char] = i

    intervals = []
    # Step 2: Form valid intervals starting at the first occurrence of each character.
    for i, char in enumerate(s):
        if i != first[char]:
            continue
        start, end = i, last[char]
        valid = True
        j = start
        # Expand and validate the interval
        while j <= end:
            c = s[j]
            if first[c] < start:
                valid = False
                break
            end = max(end, last[c])
            j += 1
        if valid:
            intervals.append((start, end))
    
    # Step 3: Sort intervals based on their end index and use greed to obtain non-overlapping substrings.
    intervals.sort(key=lambda x: x[1])
    res = []
    prev_end = -1
    for start, end in intervals:
        if start > prev_end:
            res.append(s[start:end + 1])
            prev_end = end
    return res

# Example usage:
print(maxNumOfSubstrings("adefaddaccc"))  # Expected Output: ["e", "f", "ccc"]
print(maxNumOfSubstrings("abbaccd"))      # Expected Output: ["d", "bb", "cc"]
← Back to All Questions