AlgoPressAppearance
0763-划分字母区间
https://leetcode.cn/problems/partition-labels
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
示例：
输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
提示：
S的长度在[1, 500]之间。 S只包含小写字母 'a' 到 'z' 。
思路【ME】
题目要求划分尽可能多的片段，因此只要条件满足的就截取一个片段 从i=0开始，因为每个字符必须包含在同一个片段中，所以 就从后面找到 = s[i] 的数字作为结尾，如果没有找到，那么 s[i] 就可以单独作为一个片段画出来
题目意思要求每隔字符必须出现在同一个片段中，所以我们从开始一个字符，查找他的最后一次出现的地方（从后往前查找）。 这样这段字符是必须在同一个片段中的。
但是还不仅限于此，我们要遍历这个区间，当发现其他的字符最后一次出现的地方大于这个区间的时候，我们要扩展这个区间的右边界。
一直到我们遍历的索引与右边界相等，说明所有字符都包含在这里了，此时更新结果集，并设置下一个查找区间。
参考代码
csharp
public class Solution {
public IList<int> PartitionLabels(string s) {
int start = 0;
int end = 0;
List<int> list = new List<int>();
for(int i=0; i<s.Length; i++){
//循环结尾
for(int j=i+1; j<s.Length; j++){
if(s[i] == s[j] && end < j){
end = j;
}
}
if(i == end){
list.Add(end-start+1);
start = i+1;
end = i+1;
}
}
return list;
}
}
csharp
public class Solution {
public IList<int> PartitionLabels(string s) {
List<int> result = new List<int>();
int end = 0;
int start = 0;
for(int i=0; i<s.Length; i++){
//从后往前查找字符最后一次出现的地方，我们查到到的第一个就是最右边界，所以可以停止继续查找
for(int j=s.Length-1;j>=i;j--){
if(s[j] == s[i]){
end = Math.Max(end,j);
break;
}
}
//如果遍历的所有字符都没有超过end，就说明可以拆分一个片段
//更新结果集，并且设置下一个区间的开始 start
if(i == end ){
result.Add(end-start+1);
start=i+1;
}
}
return result;
}
}
复习：20220514
csharp
public class Solution {
public IList<int> PartitionLabels(string s) {
int start = 0;
int end = 0;
List<int> result = new List<int>();
for(int i=0; i<s.Length; i++){
for(int j=s.Length-1; j>=i; j--){
if(s[j] == s[i]){
end = Math.Max(end,j);
break;
}
}
if(i == end){
result.Add(i-start+1);
start = i+1;
}
}
return result;
}
}