划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。

  • 输入：s = “ababcbacadefegdehijhklij”

  • 输出：[9,7,8]

  • 解释：
    划分结果为 “ababcbaca”、”defegde”、”hijhklij” 。
    每个字母最多出现在一个片段中。
    像 “ababcbacadefegde”, “hijhklij” 这样的划分是错误的，因为划分的片段数较少。

  • 输入：s = “eccbbbbdec”

  • 输出：[10]

思路

先统计每个字符的结束位置，再根据结束位置做切割

解题方法

统计每个字符结束位置，放入哈希表中
遍历字符串，找寻一定范围内字符最远出现的下标位置
当最远下标位置等于当前下标，说明找到一个分割点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var partitionLabels = function(s) {
    // 先找每个字母的边界，为了找一定范围内最大值
    // 到达当前可找的最大边界，则记录一下长度，进而开始统计下一段字符的长度
    var hash = {}
    for (var i = 0; i < s.length; i++) {
        hash[s.charAt(i)] = i
    }
    var res = []
    var left = 0 // 记录分割位置的起点
    var right = 0 // 记录当前范围可达最大边界
    for (var i = 0; i < s.length; i++) {
        right = Math.max(right, hash[s.charAt(i)]) // 不断找每个范围内可达的最大边界
        if (right === i) { // 到达该范围内可达最大边界，说明可以分割
            res.push(right - left + 1)
            left = i + 1 // 分割位置起点为下一个索引
        }
    }

    return res
};