Leetcode 763.Partition Labels
题目：
A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts
Example 1:
Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.
这题采用贪心算法解，主要思路是先从后往前找到第0 个字符最后一次出现的索引计为i，再遍历0到i中的每个字符，找出最后一次出现的索引，若比i大则更新i，直到结束，这样0到i就是一个最小分区。接下来对i+1之后也做同样的处理。
f方法就对所给出的索引进行分区处理。
Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.
这题采用贪心算法解，主要思路是先从后往前找到第0 个字符最后一次出现的索引计为i，再遍历0到i中的每个字符，找出最后一次出现的索引，若比i大则更新i，直到结束，这样0到i就是一个最小分区，
class Solution {
public List<Integer> partitionLabels(String s) {
List<Integer> result = new ArrayList<>();
if (s == null || s.length() == 0) {
return result;
}
if (s.length() == 1) {
result.add(0);
return result;
}
int i = f(0, s);
int j = 0;
while (i < s.length()) {
if (i == -1)
break;
result.add(i + 1 - j);
j = i + 1;
i = f(i + 1, s);
}
return result;
}
int f(int index, String s) {
int n = index;
if (index >= s.length())
return -1;
for (int i = index; i < n + 1; i++) {
for (int j = s.length() - 1; j >= 0; j--) {
if (s.charAt(i) == s.charAt(j)) {
if (j > n) {
n = j;
}
break;
}
}
}
return n;
}
}