const ALPHABET_SIZE: usize = 26;

impl Solution {
    pub fn partition_labels(s: String) -> Vec<i32> {
        // Compute first and last occurrence of each character, and their order of appearance
        let (first_pos, last_pos, char_order) = Self::build_char_ranges(&s);

        let mut result = Vec::new();
        let mut current_right = -1;
        let mut prev_split = -1;

        // Greedily merge character intervals to form partitions
        for c in char_order {
            // If current interval starts after previous merged one, cut the partition
            if first_pos[c] > current_right && current_right > prev_split {
                result.push(current_right - prev_split);
                prev_split = current_right;
            }
            // Extend current interval to include this character
            current_right = current_right.max(last_pos[c]);
        }

        // Append the final partition
        result.push(s.len() as i32 - 1 - prev_split);

        result
    }

    // build_char_ranges collects first/last positions of characters and their first-seen order
    fn build_char_ranges(s: &str) -> ([i32; ALPHABET_SIZE], [i32; ALPHABET_SIZE], Vec<usize>) {
        let mut first_pos = [i32::MAX; ALPHABET_SIZE];
        let mut last_pos = [i32::MIN; ALPHABET_SIZE];
        let mut char_order = Vec::new();

        // Traverse string to fill positions and track first-seen character order
        for (i, ch) in s.chars().enumerate() {
            let idx = (ch as u8 - b'a') as usize;
            let i = i as i32;
            if i < first_pos[idx] {
                first_pos[idx] = i;
                char_order.push(idx); // First time we see this character
            }
            last_pos[idx] = i;
        }

        (first_pos, last_pos, char_order)
    }
}