Leetcode 划分字母区间

时间：2024-10-17 07:24:44

在这里插入图片描述

题目要求：

将字符串 s 划分成尽量多的片段，保证每个片段中出现的字母不会出现在其他片段中。

具体解释如下：

  1. 尽量多的片段：题目要求的是在划分过程中，我们要尽量让划分的片段数量最大化，而不是最少化。每次划分的片段应当符合下述条件。

  2. 字母不会出现在其他片段中：对于每个划分出的片段，片段中的每个字母只能在该片段内出现，不能在其他片段中再出现。换句话说，每个字母都必须包含在一个完整的片段中，且不能跨越多个片段。

划分过程：

为了满足这个要求，划分的基本思路是：

  • 从头开始遍历字符串，对于当前遇到的字符，找到它在字符串中最后一次出现的位置。
  • 继续遍历，更新片段的结束位置（当前片段中所有字符的最远出现位置）。
  • 当遍历到的字符索引正好是该片段的结束位置时，就可以划分出一个片段。
  • 然后继续处理剩下的字符串，直到整个字符串都被划分完毕。

这种做法能保证每个片段中的所有字母都只出现在这个片段中，同时也能保证片段数量是最多的。

举个例子：

对于字符串 s = "ababcbacadefegdehijhklij"，划分过程如下：

  1. 从第一个字符 'a' 开始，找到 'a' 的最后出现位置是索引 8，同时还要考虑字符 'b' 和 'c' 的最后出现位置是索引 5 和 7。因此，第一个片段应该是从索引 0 到索引 8，片段为 "ababcbaca"。

  2. 接着从索引 9 开始，处理下一个字符 'd'，找到 'd' 的最后出现位置是索引 14，字符 'e' 的最后位置是索引 15。所以第二个片段是从索引 9 到索引 15，片段为 "defegde"。

  3. 最后，处理从索引 16 开始的部分，字符 'h'、'i'、'j' 的最后出现位置分别是索引 19、22 和 23。因此第三个片段是从索引 16 到索引 23，片段为 "hijhklij"。

因此，最终的划分结果为：[9, 7, 8]，即 "ababcbaca"、"defegde" 和 "hijhklij"。

这种划分方式能确保每个片段中的字母不会出现在其他片段中，并且片段的数量是最大化的。

java solution

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> result = new ArrayList<>();
        int[] lastIndex = new int[26];
        //统计 s 中每个字符的最后出现位置下标
        for(int i = 0; i < s.length(); ++i) {
            lastIndex[s.charAt(i) - 'a'] = i;
        }

        int start = 0, end = 0;
        for(int i = 0; i < s.length(); ++i) {
            //先根据当前字符的最后出现位置下标更新end
            end = Math.max(end, lastIndex[s.charAt(i) - 'a']);
            if(i == end) {
                result.add(end - start + 1);
                start = end + 1;
            }
        }
        return result;
    }
}

相关文章