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

内容：

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

解题思路：

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

2. 逐步确定每个子串的边界：然后我们通过遍历字符串，在遍历的过程中，我们会不断更新当前子串可能扩展到的最远位置（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) 时间内完成问题的解决。通过这种方法，我们可以高效地解决类似的问题。