Typescript-Algorithms
    Preparing search index...

    Variable partition_labelsConst

    partition_labels: (s: string) => number[] = partitionLabels

    763.划分字母区间

    给你一个字符串 s。请你将 s 划分为尽可能多的片段,同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。


    输入: s = "ababcbacadefegdehijhklij"

    输出: [9,7,8]

    解释:

    • 第一个片段 "ababcbaca"(长度9),包含了从第一个a到最后一个a之间的所有字符。
    • 第二个片段 "defegde"(长度7),包含了从第一个d到最后一个e之间的所有字符。
    • 第三个片段 "hijhklij"(长度8),包含了从第一个h到最后一个j之间的所有字符。

    输入: s = "eccbbbbdec"

    输出: [10]


    • 1 <= s.length <= 500
    • s 仅由小写英文字母组成

    Type declaration

      • (s: string): number[]
      • Parameters

        • s: string

        Returns number[]

    算法的核心思想是:每个字符只能出现在一个片段中,所以片段必须包含该字符的所有出现位置。

    1. 遍历字符串,记录每个字符最后出现的位置
    2. 遍历字符串,记录当前片段的结束位置
    3. 如果当前位置是结束位置,说明当前片段已经可以结束了。也可以看成i追上了end,说明当前片段已经可以结束了。
    4. 更新start为下一个片段的起始位置