划分字母区间

力扣 763. 划分字母区间

题目说明

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

提示：

S的长度在[1, 500]之间。
S只包含小写字母 'a' 到 'z' 。

示例

示例 1:

输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

笔者理解

此题是一道字符串算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，我们可以记录每个字母最后出现的位置，然后通过标记的方式来划分字符串，让我们来看看具体如何实现的吧。

实现

class Solution {
    /**
     * 哈希表
     */
    public List<Integer> partitionLabels(String s) {
        List<Integer> result = new ArrayList<>();

        // 哈希表存储字符最后出现的位置
        HashMap<Character, Integer> map = new HashMap<>();

        char[] chars = s.toCharArray();

        int length = chars.length;

        for (int i = 0; i < length; i++) {
            map.put(chars[i], i);
        }

        int left = 0;
        int right = map.get(chars[left]);

        while (right < length) {
            // 看有没有字符出现的位置在更后面
            int tick = left + 1;
            while (tick < right) {
                if (map.get(chars[tick]) > right) {
                    // 然后有就将右边界向后移
                    right = map.get(chars[tick]);
                }
                tick++;
            }

            // 记录区间
            result.add(right - left + 1);

            left = right + 1;
            if (left >= length) {
                break;
            }
            right = map.get(chars[left]);
        }

        return result;
    }
}