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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Non-Overlapping Substrings

Difficulty: Hard

Problem Description

Given a string s of lowercase letters, you need to find the maximum number of non-empty substrings of s that do not overlap and contain all occurrences of each character within them. If there are multiple solutions with the same number of substrings, return the one with the minimum total length.

Key Insights

  • Substrings must include all occurrences of any character they contain.
  • The substrings cannot overlap, meaning they must be disjoint.
  • A greedy approach can be used to maximize the number of substrings while minimizing their total length.
  • The solution must account for the last occurrence of each character to determine valid substring boundaries.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s. Space Complexity: O(1), since we are only using a fixed amount of additional space regardless of the input size.

Solution

The solution involves two main steps:

  1. Determine Boundaries: For each character in the string, find the first and last occurrence. This helps in defining the boundaries of the substrings.
  2. Greedy Selection: Iterate through the string, and for each potential substring defined by the previous step, check if it can be included in the final result without overlapping with previously selected substrings. Select substrings based on their boundaries while ensuring they do not overlap.

Code Solutions

def maxNumOfSubstrings(s: str):
    n = len(s)
    first = [0] * 26
    last = [0] * 26
    
    # Step 1: Find first and last occurrences
    for i in range(n):
        index = ord(s[i]) - ord('a')
        if first[index] == 0:
            first[index] = i + 1  # Store 1-based index
        last[index] = i + 1  # Store 1-based index

    # Step 2: Find valid substrings
    intervals = []
    for i in range(26):
        if first[i] == 0: continue  # No occurrence of this character
        l, r = first[i] - 1, last[i] - 1
        for j in range(l, r + 1):
            if last[ord(s[j]) - ord('a')] > r:
                r = last[ord(s[j]) - ord('a')] - 1
        intervals.append((l, r))
    
    # Step 3: Sort intervals based on the end index
    intervals.sort(key=lambda x: (x[1], x[0]))
    result = []
    last_end = -1
    
    for l, r in intervals:
        if l > last_end:
            result.append(s[l:r + 1])
            last_end = r
    
    return result
← Back to All Questions