763. 划分字母区间#

作为一名开发者，你一定遇到过需要分割字符串的场景。今天我们来聊聊LeetCode 763题，一个看似简单实则暗藏玄机的字符串划分问题。

📝 问题的精髓#

题目要求我们把字符串划分成尽可能多的片段，使得同一个字母只会出现在其中的一个片段中。比如说：

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

plaintext

乍一看，这个问题似乎有点让人摸不着头脑。但别着急，让我们一起来剖析它的本质。

问题描述#

题目目标#

给定一个字符串 s ，请尽可能多地划分为若干片段，使得每个字母最多出现在一个片段中。返回一个表示每个片段长度的列表。

示例 1#

输入： s = "ababcbacadefegdehijhklij" 输出： [9,7,8] 说明： 把输入和输出放在一起看，会更容易直接抓住题目要求的变化。

💡 思路启发：贪心的艺术#

想象你在玩一个特殊的拼图游戏。每个字母就像一块特殊的拼图块，它可能在字符串的多个位置出现。如果某个字母出现在位置A和位置B，那么从A到B之间的所有字母都必须在同一个片段中。

这就是解决问题的关键：我们需要找到每个字母最后出现的位置，然后确定每个片段的边界。这听起来是不是有点像贪心算法？

⚡ 代码实现：优雅与效率的平衡#

class Solution {
    public List<Integer> partitionLabels(String s) {
        // lastPos[26]：记录每个小写字母在字符串中“最后一次出现”的下标
        // 例如 lastPos[0] 对应字母 'a' 的最后位置
        int[] lastPos = new int[26];
        // 第一次遍历：预处理每个字符的最后出现位置
        for (int i = 0; i < s.length(); i++) {
            // s.charAt(i) - 'a'：把字符映射为 0~25 的数组下标
            // 用当前下标 i 覆盖写入，最终保留的就是“最后出现位置”
            lastPos[s.charAt(i) - 'a'] = i;
        }

        // result：保存每个划分片段的长度
        List<Integer> result = new ArrayList<>();
        // start：当前片段起始下标
        // end：当前片段必须延伸到的最远下标（由片段内字符的最后出现位置共同决定）
        int start = 0, end = 0;

        // 第二次遍历：根据 lastPos 动态确定每个片段的右边界
        for (int i = 0; i < s.length(); i++) {
            // 当前位置字符的最后出现位置，可能把当前片段右边界继续向右推
            // 贪心点：end 始终是“当前片段内所有字符最后出现位置”的最大值
            end = Math.max(end, lastPos[s.charAt(i) - 'a']);

            // 当 i 走到 end，说明 [start, end] 已经是一个完整且合法的片段
            // 因为这个片段内任意字符都不会在 end 之后再次出现
            if (i == end) {
                // 片段长度 = 右边界 - 左边界 + 1
                result.add(end - start + 1);
                // 开启下一个片段：起点移动到下一个位置
                start = i + 1;
            }
        }

        // 返回所有片段长度
        return result;
    }
}

java

这段代码的精妙之处在于它巧妙地运用了贪心的思想。让我们来看看它是如何工作的：

首先，我们用一个数组记录每个字母最后出现的位置。这就像是在为每个字母画一个范围，标记它们的势力范围。

然后，我们用双指针技术来确定每个片段的边界。start指针标记当前片段的起始位置，end指针则会随着遍历动态更新，始终指向当前片段中所有字母的最远位置。

当我们遍历到end位置时，就意味着找到了一个完整的片段。为什么？因为这个位置之后不会再出现任何属于当前片段的字母了。

🎯 复杂度与优化#

时间复杂度是O(n)，因为我们只需要遍历两次字符串。空间复杂度是O(1)，因为我们使用的额外空间（lastPos数组）大小是固定的26。

有趣的是，这个解法已经是最优解了。因为我们必须至少遍历一次字符串来收集字母的位置信息，然后再遍历一次来划分片段。

💡 举一反三#

这道题的思想可以应用到很多类似的问题中：

区间合并问题
会议室安排问题
任务调度问题

关键是要找到问题中的”不可分割性”特征，然后用贪心的思想来解决。

🤔 思考题#

如果我们要求每个片段中的字母必须完全相同，比如”aaabbb”应该划分为[“aaa”,“bbb”]，该如何修改我们的解法呢？

📝 面试技巧#

在面试中遇到这类问题，建议按以下步骤思考：

首先阐述问题的关键点 - 每个字母只能出现在一个片段中，这暗示了我们需要考虑字母的完整范围。然后解释为什么贪心算法是合适的 - 因为我们总是希望让每个片段尽可能小，同时满足条件。最后，可以谈谈如何处理边界情况，以展示你考虑问题的全面性。

记住，有时候面试官可能会问到如何处理超大规模的输入。这时候可以讨论使用流式处理或者分布式计算的可能性。

如果这篇文章对你有帮助，别忘了点赞关注！我们每周都会带来高质量的算法讲解，一起在算法之路上进步！