问题：763. 划分字母区间

分析

分析：为了切分最多的字符串，我们希望每个字符串尽可能的短，这一步即为贪心的思想。

但是我们如何保证我们切分的字符串是符合题目意思的呢？拿S为例子：

变量说明：stratIndex：当前子串的开始下标，rearIndex当前子串的结尾下标。

首先：a字符最后出现的下标为8，我们假设第一个字符的长度为a第一次出现到最后一次出现的长度，这个是可能的最小的长度，此时得到了子串s1，其startIndex为0，rearIndex为8；

为了保证s1是满足条件的，我们遍历s1的子串中的元素是否都满足题目的要求，即从b开始，再判断b最后一次出现的位置是否是在子串内，对于s1来说是满足的，即在0-8内的字符出现的位置都没有超过这个范围；

遍历完s1你会发现长度刚好为9，此时从d开始找，d的下标为9，最后一次出现的下标为14，此时子串的长度为6，那么我们开始检查我们的子串s2；

从9开始，一直到当前的rearIndex，**注意这个rearIndex可能是会更新的。**对于s2来说，e的出现范围超过了一开始记录的rearIndex，**那么我们需要更新rearIndex，以记录正确的子串长度。**最终s2的startIndex为9，rearIndex为15,。

对于s3来说也是一样的。

注意：字符串"qiejxqfnqceocmy"是一种需要注意的情况：

首先看q最后一次出现的位置为8，即startIndex=0，rearIndex=8。检测字符串：在原来的子串中的字符只有e出现在了子串范围之外，那么更新到e最后一次出现的位置，此时c被包括进来了，c最后一次出现的位置为12，即某次的rearIndex更新可能会引发更多的rearIndex更新，所以在检查字符串的时候，我们应该从startInde一直检查到最新的rearIndex。

Code

class Solution { public List<Integer> partitionLabels(String S) { List<Integer> ls = new ArrayList(); if (S.length() == 0) return ls; char[] chars = S.toCharArray(); // 用于从后向前找到最后一个出现的字符的下标。 int rearIndex = chars.length, arrLength = chars.length; for (int startIndex = 0; startIndex < arrLength; startIndex = ++rearIndex) { rearIndex = arrLength; char ch = chars[startIndex]; while (--rearIndex > startIndex && ch != chars[rearIndex]); // 保证我们的贪心策略是正确的 // 我们需要检查我们找的序列是否满足条件 int count = rearIndex; int num = startIndex; // 这里一定是小于count，因为你新加入的字符也可能导致最后的字符串变长 while (++num < rearIndex) { ch = chars[num]; int index = arrLength; while (--index > count && ch != chars[index]); count = index; } rearIndex = count; // 存储长度 ls.add(rearIndex - startIndex + 1); } return ls; } }

结果