划分字母区间

Question

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是s。

返回一个表示每个字符串片段的长度的列表。

思路

可以分为如下两步：

统计每一个字符最后出现的位置
从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

var partitionLabels = function(s) {
    let hash = new Array(27,0)       // i为字符，hash[i]为字符出现的最后位置
    for(let i=0;i<s.length;i++){     //统计每一个字符最后出现的位置
        hash[s[i]] = i
    }
    let res = []
    let farest = 0
    let last = 0
    for(let i=0;i<s.length;i++){
        farest = hash[s[i]]>farest?hash[s[i]]:farest
        if( hash[s[i]] === farest && hash[s[i]] === i ) {
            res.push(i-last+1)
            last = i+1
        }
    }
    return res
};

划分字母区间 ​

思路 ​

划分字母区间

思路