763. Partition labels

#include <stdlib.h>
#include <string.h>

int *partitionLabels(char *s, int *returnSize) {
  int n = strlen(s);
  int last[26];
  for (int i = 0; i < n; i++)
    last[s[i] - 'a'] = i;

  // at most one partition per character
  int *result = malloc((n > 0 ? n : 1) * sizeof(int));
  int count = 0, start = 0, end = 0;

  for (int i = 0; i < n; i++) {
    if (last[s[i] - 'a'] > end)
      end = last[s[i] - 'a'];
    if (i == end) {
      result[count++] = end - start + 1;
      start = i + 1;
    }
  }

  *returnSize = count;
  return result;
}

#include <algorithm>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
  vector<int> partitionLabels(string s) {
    int last[26];
    for (int i = 0; i < s.size(); i++)
      last[s[i] - 'a'] = i;

    vector<int> result;
    int start = 0, end = 0;

    for (int i = 0; i < s.size(); i++) {
      end = max(end, last[s[i] - 'a']);
      if (i == end) {
        result.push_back(end - start + 1);
        start = i + 1;
      }
    }

    return result;
  }
};

package greedy

func partitionLabels(s string) []int {
    var last [26]int
    for i := 0; i < len(s); i++ {
        last[s[i]-'a'] = i
    }

    result := []int{}
    start, end := 0, 0

    for i := 0; i < len(s); i++ {
        end = max(end, last[s[i]-'a'])
        if i == end {
            result = append(result, end-start+1)
            start = i + 1
        }
    }

    return result
}

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] last = new int[26];
        for (int i = 0; i < s.length(); i++)
            last[s.charAt(i) - 'a'] = i;

        List<Integer> result = new ArrayList<>();
        int start = 0, end = 0;

        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, last[s.charAt(i) - 'a']);
            if (i == end) {
                result.add(end - start + 1);
                start = i + 1;
            }
        }

        return result;
    }
}

/**
 * @param {string} s
 * @return {number[]}
 */
var partitionLabels = function (s) {
  const last = new Map();
  for (let i = 0; i < s.length; i++) last.set(s[i], i);

  const result = [];
  let start = 0,
    end = 0;

  for (let i = 0; i < s.length; i++) {
    end = Math.max(end, last.get(s[i]));
    if (i === end) {
      result.push(end - start + 1);
      start = i + 1;
    }
  }

  return result;
};

from typing import List


class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last = {c: i for i, c in enumerate(s)}

        result = []
        start = end = 0

        for i, c in enumerate(s):
            end = max(end, last[c])
            if i == end:
                result.append(end - start + 1)
                start = i + 1

        return result

impl Solution {
    pub fn partition_labels(s: String) -> Vec<i32> {
        let s = s.as_bytes();
        let mut last = [0; 26];
        for (i, &c) in s.iter().enumerate() {
            last[(c - b'a') as usize] = i;
        }

        let mut result = Vec::new();
        let (mut start, mut end) = (0, 0);

        for (i, &c) in s.iter().enumerate() {
            end = end.max(last[(c - b'a') as usize]);
            if i == end {
                result.push((end - start + 1) as i32);
                start = i + 1;
            }
        }

        result
    }
}