מריה בוטוסוב

נותנים מחרוזת של אותיות קטנות באנגלית. יש לחלק אותה למחיצות. כל מחיצה מכילה אותיות חוזרות או לא חוזרות מאותה קבוצה. נותנים מחרוזת: "ababcbacadefegdehijhklij", התשובה תהיה [9,7,8]

public IList<int> PartitionLabels(string S) {
    List<int> segments = new List<int>();
    if (S == null || S.Length == 0)
        return segments;
        
    int[] last = new int[26];      
    for (int i = 0; i < S.Length; i++)
        last[S[i] - 'a'] = i;        
 
    int end = 0, start = 0;        
    for (int i = 0; i < S.Length; i++) {
        end = Math.Max(end, last[S[i] - 'a']);
        if(i == end) {
            segments.Add(end - start + 1);
            start = end+ 1;   
        }
    }
    return segments;
}