《LeetCode763.划分字母区间|高效分割字符串》

内容：

问题描述： 给定一个字符串 S，将字符串分割成若干个子串，使得每个子串中的字符都不重复，并且返回每个子串的长度。

解题思路：

找到每个字符最后一次出现的位置：我们首先遍历一遍字符串，记录下每个字符最后出现的索引。这帮助我们确定哪些字符必须出现在同一个子串中。

逐步确定每个子串的边界：然后我们通过遍历字符串，在遍历的过程中，我们会不断更新当前子串可能扩展到的最远位置（end），直到当前遍历到的位置 i 和 end 相等时，说明从 start 到 i 的这一段可以独立成一部分，加入答案。

代码实现：

class Solution { public List<Integer> partitionLabels(String S) { char[] s = S.toCharArray(); int n = s.length; int[] last = new int[26]; // 记录每个字符最后出现的位置 for (int i = 0; i < n; i++) { last[s[i] - 'a'] = i; } List<Integer> ans = new ArrayList<>(); int start = 0, end = 0; // 遍历字符串，确定每个子串的边界 for (int i = 0; i < n; i++) { end = Math.max(end, last[s[i] - 'a']); if (end == i) { ans.add(end - start + 1); start = i + 1; } } return ans; } }

时间复杂度分析：

时间复杂度为 O(n)，其中 n 是字符串 S 的长度。遍历一次字符串，时间复杂度是线性的。

空间复杂度分析：

空间复杂度为 O(1)，除了输入输出之外，我们只使用了常数大小的空间（last 数组）。

总结： 这道题考察了字符串分割和字符定位的能力，通过记录每个字符最后出现的位置，能够有效地确定分割点，并在 O(n) 时间内完成问题的解决。通过这种方法，我们可以高效地解决类似的问题。