763. Partition Labels

partition-labels.go

// https://leetcode.com/problems/partition-labels/
//
// Time: O(n)
// Space: O(1)
//
// n = number of letters in string

// .................... //

func partitionLabels(s string) []int {
    last := [26]int{}
    for i := range s {
        idx := s[i] - 'a'
        last[idx] = i
    }

    res := make([]int, 0)

    start, end := 0, 0
    for i := range s {
        li := s[i] - 'a'
        if last[li] > end {
            end = last[li]
        }
        if i == end {
            res = append(res, end-start+1)
            start = end + 1
        }
    }

    return res
}