LeetCode-763 划分字母区间

Table of Contents

LeetCode-763 划分字母区间 #

Solution 1 #

每个字符出现的第一次和最后一次必须在同一个区间内, 遍历的过程中不断更新当前区间最远需要到哪里.

代码如下:

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        n = len(s)
        book = [0 for _ in range(26)]
        for i, ch in enumerate(s):
            book[ord(ch) - ord('a')]= i
        ans = []
        start = end = 0
        for i, ch in enumerate(s):
            end = max(end, book[ord(ch) - ord('a')])
            if i == end:
                ans.append(end - start + 1)
                start = end + 1
        return ans