题目描述

解题思路

一想到分割字符串就想到了回溯，但本题其实不用回溯去暴力搜索。
题目要求同一字母最多出现在一个片段中，那么如何把同一个字母的都圈在同一个区间里呢？
如果没有接触过这种题目的话，还挺有难度的。
在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。
可以分为如下两步：

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

public List<Integer> partitionLabels(String s) {
    List<Integer> list = new ArrayList<>();
    char[] chars = s.toCharArray();
    int[] edge = new int[26]; // 表示每个字母对应的最大出现的位置
    int idx = 0;    // 表示当前索引
    int last = -1;  // 默认为-1，相减就不用+1，就直接能求出长度（只是第一步）,后边的几步相减就是尾减尾
    // 找到每个数组的最大出现位置
    for (int i = 0; i < chars.length; i++) {
        edge[chars[i] - 'a'] = i;
    }
    for (int i = 0; i < chars.length; i++) {
        idx = Math.max(idx, edge[chars[i] - 'a']);  // 获取当前最大的边界
        if (i == idx) {  // 如果等于当前最大边界
            list.add(i - last); // 将边界加入结果集
            last = i;
        }
    }
    return list;
}

• 时间复杂度：O(n)
• 空间复杂度：O(1)，使用的hash数组是固定大小