JAVA练习353- 划分字母区间

题目概览给你一个字符串s。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。例如字符串ababcc能够被分为[abab, cc]但类似[aba, bcc]或[ab, ab, cc]的划分是非法的。注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是s。返回一个表示每个字符串片段的长度的列表。示例 1输入s ababcbacadefegdehijhklij输出[9,7,8]解释划分结果为 ababcbaca、defegde、hijhklij 。 每个字母最多出现在一个片段中。 像 ababcbacadefegde, hijhklij 这样的划分是错误的因为划分的片段数较少。示例 2输入s eccbbbbdec输出[10]提示1 s.length 500s仅由小写英文字母组成来源763. 划分字母区间 - 力扣LeetCode解题分析方法贪心要知道同一字母是否重复出现我们需要先遍历一次字符串存储每个字母最后出现的索引。然后再遍历字符串令当前索引为 i子串的起始索引为 start结束索引为 end那么当前子串的结束索引一定是 子串中所有字母对应最后索引 的最大值因此每次遍历记录最大值 end当 end i 时说明改子串已没有重复字母记录长度为 end - start 1然后遍历下一个子串 即 start end 1end 跟着下个子串更新时间复杂度O(n)空间复杂度O(26)class Solution { public ListInteger partitionLabels(String s) { int[] letterIndex new int[26]; int n s.length(); for (int i 0; i n; i) { letterIndex[s.charAt(i) - a] i; } int start 0, end 0; ListInteger result new ArrayList(); for (int i 0; i n; i) { end Math.max(end, letterIndex[s.charAt(i) - a]); if (end i) { result.add(end - start 1); start end 1; } } return result; } }