【Leetcode 热题 100】763. 分别字母区间

题目配景

给你一个字符串                                    s                              s                  s。我们要把这个字符串分别为尽可能多的片断，同一字母最多出如今一个片断中。
注意，分别效果必要满意：将所有分别效果按次序毗连，得到的字符串仍然是                                    s                              s                  s。
返回一个表现每个字符串片断的长度的列表。
数据束缚

●                                    1                         ≤                         s                         .                         l                         e                         n                         g                         t                         h                         ≤                         500                              1 \le s.length \le 500                  1≤s.length≤500
●                                    s                              s                  s 仅由小写英笔墨母组成
解题过程

看到频率和子串，一开始想的是滑窗搭配哈希表，实际上并不是很好实现。
比力好的做法是，找到所有字母第一次和最后一次出现的位置，把这个题目看作 归并区间。
每个字母第一次和最后一次出现的位置会框定一个范围，这些范围里还会包含其它字母，也就产生了重叠区间。为了使得同一字母最多出如今一个片断中，这些重叠区间是必要归并的。
而标题又要求分别为尽可能多的片断，就不应该进一步地实验归并区间了，以是上述处理完的区间长度就是终极效果。
详细实现

1. class Solution {
2.     public List<Integer> partitionLabels(String s) {
3.         char[] chS = s.toCharArray();
4.         int n = chS.length;
5.         // 统计每一个字母最后一次出现的位置
6.         int[] lastIndex = new int[26];
7.         for (int i = 0; i < n; i++) {
8.             lastIndex[chS[i] - 'a'] = i;
9.         }
10.         List<Integer> res = new ArrayList<>();
11.         for (int i = 0, left = 0, right = 0; i < n; i++) {
12.             // 更新当前有边界的要求
13.             right = Math.max(right, lastIndex[chS[i] - 'a']);
14.             // 访问到当前的有边界时，说明已经完成了区间合并，添加结果并移动左边界指针
15.             if (i == right) {
16.                 res.add(right - left + 1);
17.                 left = i + 1;
18.             }
19.         }
20.         return res;
21.     }
22. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。