3458. Select K Disjoint Special Substrings

from typing import List

class Solution:
    def maxSubstringLength(self, s: str, required_count: int) -> bool:
        """
        Determines whether there are at least 'required_count' valid substrings (intervals)
        in the string 's' that satisfy the following conditions:
          - For each interval [start, end] obtained by taking the first occurrence of a character,
            the interval is extended to include all later occurrences of letters within it.
          - The interval is valid only if no letter within it has its first occurrence before 'start'.
          - The interval that spans the entire string is ignored.
        Returns True if the number of such non-overlapping intervals is at least 'required_count'; otherwise, False.
        """
        n = len(s)
        # Initialize arrays to store the first and last occurrence indices for each letter (a-z)
        first_occurrence = [-1] * 26
        last_occurrence = [-1] * 26
        
        # Populate first_occurrence and last_occurrence for each character in the string
        for i, ch in enumerate(s):
            idx = ord(ch) - ord('a')
            if first_occurrence[idx] == -1:
                first_occurrence[idx] = i
            last_occurrence[idx] = i
        
        # List to store valid intervals as tuples (start_index, end_index)
        intervals = []
        
        # Iterate through each character position in the string
        for i in range(n):
            idx = ord(s[i]) - ord('a')
            # Only consider positions that are the first occurrence of that character
            if i != first_occurrence[idx]:
                continue
            
            # Initialize the interval's end index to the last occurrence of the current character
            j = last_occurrence[idx]
            pos = i
            # Expand the interval [i, j] to include all occurrences of characters found within it
            while pos <= j:
                current_idx = ord(s[pos]) - ord('a')
                j = max(j, last_occurrence[current_idx])
                pos += 1
            
            # Validate the interval: no character inside the interval should have its first occurrence before i
            valid_interval = True
            for pos in range(i, j + 1):
                current_idx = ord(s[pos]) - ord('a')
                if first_occurrence[current_idx] < i:
                    valid_interval = False
                    break
            if not valid_interval:
                continue
            
            # Skip the interval that covers the entire string
            if i == 0 and j == n - 1:
                continue
            
            intervals.append((i, j))
        
        # Sort intervals based on their ending index for greedy selection
        intervals.sort(key=lambda interval: interval[1])
        
        # Use a greedy algorithm to count non-overlapping intervals
        partition_count = 0
        current_end = -1
        for start, end in intervals:
            if start > current_end:
                partition_count += 1
                current_end = end
        
        # Return True if the number of valid partitions is at least the required count; else, False.
        return partition_count >= required_count