Участник:ArtemTovkes/maximum-number-of-non-overlapping-substrings

Материал из DISCOPAL
Перейти к: навигация, поиск

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

class Solution:
    def maxNumOfSubstrings(self, s: str) -> List[str]:
        n = len(s)
        pos = defaultdict(list)
        for i,c in enumerate(s):
            pos[c].append(i)
        res = []
        currBoundary = -1
        for i in range(n):
            if i != pos[s[i]][0]:
                continue
            right = pos[s[i]][-1]
            j = i+1
            while j<right:
                if pos[s[j]][0]<i:
                    right = -1
                    break
                right = max(right,pos[s[j]][-1])
                j += 1
 
            if right == -1:
                continue
            if i<currBoundary:
                res.pop()
            res.append(s[i:right+1])
            currBoundary = right
        return res