Crack the Backend

Problem Statement

Given a string s (lowercase English letters), partition s into as many parts as possible so that each letter appears in at most one part. Return a list of integers representing the size of each part. (So no letter appears in two different parts.)

Key Observations

For each character, we need to know its last occurrence in s. When we are building a partition starting at start, we extend the "current end" to the maximum last index of any character we have seen so far. When our index i reaches this end, we have completed a partition (all chars in this segment appear only in this segment); we record the length end - start + 1, then set start = end + 1 and continue.

Approach

High-level: Precompute last index of each char. start=0, end=0. For i=0..n-1: end = max(end, last[s[i]]). If i==end: result.add(end-start+1), start = end+1. Return result.

Steps: int[] last = new int[26]; for i in 0..n-1 last[s[i]-'a']=i. start=0, end=0; for i: end=max(end, last[s.charAt(i)-'a']); if i==end add (end-start+1), start=end+1.

Implementation

Java

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 = end + 1; }
    }

    return result;
}

Test Cases

Example 1

Input

s = "ababcbacadefegdehijhklij"

Expected

[9,7,8]

Explanation

Partitions "ababcbaca", "defegde", "hijhklij".

Complexity Analysis

Time: typically O(n) or O(n log n).
Space: O(1) or O(n).

Follow-ups

Prove greedy choice property; handle ties.