~/leetcode$cat1520. Maximum Number of Non-Overlapping Substrings

For each valid substring, it must start with the first occurrence of a character and end with the last occurrence of the character. Therefore, there are maximum of 26 possible substrings (a - z) and we can figure out the start, end and the length of each substring by taking the first and last occurrence of each character in the string.

After we find this out, we can do another pass over the string to find which letters are in each substring. If a substring contains other letters, the substring will expand (the starting index will be the minimum of the two starting indices and the end index will be the maximum of the ending indices).

For example, “ababb”, originally will have a: [0, 2] and b: [1, 4], and in the second pass, we find that a and b substrings both contain each other. Therefore, the new substring will be ab: [min(0, 1), max(2, 4)] = ab: [0, 4].

After we get this valid set of substrings, we want to get the maximum number of valid substrings that do not overlap out of this set. If we have any ties, we can use the sum of the length of the substrings and return the minimum.

The list should already be sorted since we do the passes in order of the string (i.e. the indices should already be in increasing order. Therefore, we can use a greedy approach where we take the intervals in order and if we can’t fit the interval into the current list of intervals that we are keeping track of, we can add a new list of intervals.

After we get this lists of list of non-overlapping intervals, we can keep track of the list of intervals with the max length, using the minimum sum length of the substrings as tiebreaker whenever we come across this situation.

Then we should just be able to return the substring represented by the final interval.

This question took way too long to implement - we could not for the life of us find a way to expand the interval properly to ensure that each substring contains all occurrences of the characters that are in it… We ended up on the union find solution (shoutout Kelvin for teaching me the implementation) - there’s got to be a better way of doing this… At least it passed am i rite

class Solution:
    def maxNumOfSubstrings(self, s: str) -> list[str]:
        first_last = {}
        # first pass
        for i, c in enumerate(s):
            if c not in first_last:
                first_last[c] = [i, i]
            first_last[c][1] = i

        inclusion = {}
        currently_in = set()
        for i, c in enumerate(s):
            for k, v in first_last.items():
                if i == v[0]:
                    currently_in.add(k)
                if i == v[1]:
                    currently_in.remove(k)

            for letter in currently_in:
                if letter != c:
                    if c not in inclusion:
                        inclusion[c] = set()
                    inclusion[c].add(letter)

        class UnionFind:
            def __init__(self):
                self.parents = [i for i in range(26)]

            def find_root(self, letter):
                if self.parents[letter] == letter:
                    return letter

                return self.find_root(self.parents[letter])

            def union(self, first_letter, second_letter):
                first_root = self.find_root(first_letter)
                second_root = self.find_root(second_letter)
                self.parents[first_root] = second_root

            def get_elements(self, root):
                res = []
                for i in range(26):
                    if self.find_root(i) == root:
                        res.append(i)
                return res

        union_find = UnionFind()
        for c, c_set in inclusion.items():
            for el in c_set:
                if el in inclusion and c in inclusion[el]:
                    c_index = ord(c) - ord('a')
                    el_index = ord(el) - ord('a')
                    union_find.union(c_index, el_index)

        roots = set()
        for i in range(26):
            root = union_find.find_root(i)
            if chr(root + ord('a')) in first_last:
                roots.add(root)

        disjoint_sets = []
        for root in roots:
            elements = union_find.get_elements(root)
            start_index = inf
            end_index = -inf
            for element in elements:
                letter = chr(element + ord('a'))
                start_index = min(start_index, first_last[letter][0])
                end_index = max(end_index, first_last[letter][1])

            disjoint_sets.append((start_index, end_index))

        intervals = []
        intervals_last_index = []
        for (start, end) in sorted(disjoint_sets, key=lambda x: x[1]):
            # find fittable intervals
            for index, curr_interval_end in enumerate(intervals_last_index):
                if start > curr_interval_end:
                    # then we can add to current interval
                    intervals[index].append((start, end))
                    intervals_last_index[index] = end
                    continue

            # if we don't find any, we need to add a new one
            intervals.append([(start, end)])
            intervals_last_index.append(end)

        result_interval = []
        result_length = 0
        for interval in intervals:
            if len(interval) > len(result_interval):
                result_interval = interval
                length = 0
                for (start, end) in interval:
                    length += end - start + 1
                result_length = length

            elif len(interval) == len(result_interval):
                length = 0
                for (start, end) in interval:
                    length += end - start + 1

                if length < result_length:
                    result_length = length
                    result_interval = interval

        result = []
        for (start, end) in result_interval:
            result.append(s[start:end + 1])

        return result

Time Complexity: O() - ceebs calculating

Space Complexity: O() - ceebs calculating

Time Taken: 1h 22m 40s

Runtime: 1718 ms

Memory: 21.8 MB

Tests Passed: 285/285