Problem statement

https://leetcode.com/problems/maximum-number-of-non-overlapping-substrings/

Solution

Let us first find the first and the last occurence for each letter. Then what we need to do is to work with intervals.

Let us iterate through letters c and for each symbol create valid substring: we start with two pointers beg = fst[c] and end = lst[c] and then on each iteration when we meet new symbol we update end. If it happen that we also need to update beg, then we can break, we are not interested in this candidate, it will be covered for another letter c. Note similarity with problem 0763 Partition Labels.

After we created intervals we can notice, that either any two of them do not intersect or one lies inside another. What question we need to answer now is to find the maximum set of not-intersecting intervals, and this is exactly the problem 0452. Minimum Number of Arrows to Burst Balloons.

Complexity

Time complexity is $O(26n)$, where $n$ is the length of string, becuase for the second stage we need only $O(26\log 26)$ time.

Code

class Solution:
    def maxNumOfSubstrings(self, s):
        fst = {c : len(s) - i - 1 for i, c in enumerate(s[::-1])}
        lst = {c : i for i, c in enumerate(s) }
        
        intervals = []
        for c in set(s):
            beg, end = fst[c], lst[c]
            bad, idx = False, beg
            
            while idx <= end:
                end = max(end, lst[s[idx]])
                if fst[s[idx]] < beg:
                    bad = True
                    break
                idx += 1

            if not bad:
                intervals.append((end, beg))
                
        ans, prev = [], -1
        for end, beg in sorted(intervals):
            if beg > prev:
                ans.append(s[beg:end + 1])
                prev = end
        
        return ans