0763. Partition Labels

题目信息

题号:

0763

难度:

Medium

主题:

字符串、区间划分、字符归属

原题:

LeetCode 0763

重点:

按原顺序把字符串切成尽可能多的连续非空片段,同一字母的全部出现位置必须落在同一片段;返回各片段长度而不是片段内容

题目重述

给定一个只含小写英文字母的字符串 s。请把它按原有顺序划分为尽可能多的连续非空片段,使任意一个字母最多只出现在其中一个片段中。所有片段依次拼接后必须恰好还原 s,不能重排或删除字符。

返回一个整数数组,按从左到右的顺序记录每个片段的长度。1 <= s.length <= 500。

自建示例

多个字符分别限定片段右边界:

输入:s = "qaqbrrsttsu"
输出:[3,1,2,4,1]
解释:可以划分为 "qaq"、"b"、"rr"、"stts" 和 "u"。两个 q 必须位于同一段,两个 r 必须位于同一段,s 与 t 的出现范围共同形成 "stts";其余字符各自只出现一次。任何一段继续切分都会让某个重复字符跨越不同片段,因此该划分的片段数量最多。

所有字符被迫留在同一片段:

输入:s = "zzzz"
输出:[4]
解释:字符 z 出现在全部四个位置。若在任意位置切分,z 都会同时出现在多个片段中,因此只能返回一个长度为 4 的片段。