public class Solution
{
public IList<int> PartitionLabels(string S)
{
var dic = new Dictionary<char, int[]>();
//记录每一个字符的第一次出现位置，和最后一次出现位置
for (int i = ; i < S.Length; i++)
{
if (!dic.ContainsKey(S[i]))
{
dic.Add(S[i], new int[] { i, i });
}
else
{
dic[S[i]][] = i;
}
}
var list = new List<int>();
int low = ;
int high = S.Length - ;
while (low <= high)
{
var c = S[low];
var i = dic[c][];//当前字符最小索引
var j = dic[c][];//当前字符最大索引
if (j == high)
{
list.Add(high - low + );
return list;
}
for (; i <= j; i++)
{
var cc = S[i];
var ii = dic[cc][];
var jj = dic[cc][];
if (jj == high)
{
list.Add(high - low + );
return list;
}
if (jj > j)
{
j = jj;
}
}
list.Add(i - low);
low = i;
} return list;
}
}
本题使用贪心算法思想，这里给出的代码是比较高效的一种解法。