763 划分字母区间

一、题目

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。

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

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

二、题解

思路：贪心。

1. 核心思路

这道题的关键是：

如果一个片段中出现了某个字符，那么这个字符在整个字符串中的最后一次出现位置，也必须被包含在这个片段中。

例如：

s = "ababcbacadefegdehijhklij"

字符 a 最后一次出现的位置是下标 8。

所以只要当前片段中包含了 a，那么当前片段至少要划分到下标 8。

因此我们可以：

先记录每个字符最后一次出现的位置。

然后从左到右遍历字符串，维护当前片段必须到达的最远位置 end。

当遍历到 i == end 时，说明当前片段中的所有字符都不会再出现在后面了，此时就可以切分出一个片段。

2. 具体步骤

  1. 第一步：遍历字符串，记录每个字母最后一次出现的位置。
  2. 第二步：再次遍历字符串，维护当前片段的起点 start 和终点 end。
  3. 第三步：遍历到每个字符时，用该字符最后一次出现的位置更新 end。
  4. 第四步：如果当前位置 i == end，说明当前片段可以结束，将长度加入结果列表。
  5. 第五步：更新下一个片段的起点 start = i + 1。

3. 关键逻辑

核心代码是：

end = Math.max(end, last[s.charAt(i) - 'a']);

含义是：

当前片段中出现过的字符，它们最后一次出现的位置都必须被包含进当前片段。

所以当前片段的右边界要不断取最大值。

当出现：

if (i == end)

说明当前位置已经到达当前片段必须覆盖的最远位置。

此时当前片段中的所有字符，都不会出现在后面的字符串中，所以可以切分。

片段长度为：

end - start + 1

然后更新下一个片段的起点：

start = i + 1;

三、代码

import java.util.*;

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> result = new ArrayList<>();

        // 1. 记录每个字母最后一次出现的位置
        int[] last = new int[26];

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            last[c - 'a'] = i;
        }

        // 2. 定义当前片段的起点和终点
        int start = 0;
        int end = 0;

        // 3. 从左到右遍历字符串，划分区间
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            // 当前片段必须包含当前字符最后一次出现的位置
            end = Math.max(end, last[c - 'a']);

            // 如果当前位置到达了当前片段的最远边界
            // 说明当前片段可以结束
            if (i == end) {
                result.add(end - start + 1);

                // 更新下一个片段的起点
                start = i + 1;
            }
        }

        // 4. 返回结果
        return result;
    }
}

四、复杂度分析

时间复杂度：O(n)O(n)

说明：需要遍历两次字符串。

第一次遍历用于记录每个字符最后一次出现的位置。

第二次遍历用于划分字符串区间。

所以时间复杂度是 O(n)O(n)。

空间复杂度：O(1)O(1)

说明：使用了一个长度为 26 的数组，记录每个小写字母最后一次出现的位置。

因为 26 是常数，所以空间复杂度是 O(1)O(1)。

评论