Partition Labels: the idea to remember.

The core insight

Record each letter's final position and extend the current partition boundary whenever a seen letter ends later.

Why it works

A partition can end only after every letter encountered inside it has finished appearing. Ending at the earliest such boundary maximizes sections.

The mistake to avoid

An early character may extend the boundary far beyond the next character's last position.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

// Java reference adapted from neetcode-gh/leetcode (MIT).
// Record each letter's final position and extend the current partition boundary whenever a seen letter ends later.
public List<Integer> partitionLabels(String s) {
    List<Integer> list = new ArrayList<>();
    HashMap<Character, Integer> map = new HashMap<>();
    for (int i = 0; i < s.length(); i++) {
        map.put(s.charAt(i), i);
    }
    int j = 0;
    int i = 0;
    while (i < s.length()) {
        int count = 0;
        j = Math.max(j, map.get(s.charAt(i)));
        while (i <= j) {
            j = Math.max(j, map.get(s.charAt(i)));
            i++;
            count++;
        }
        list.add(count);
    }
    return list;
}

Java reference adapted from neetcode-gh/leetcode · MIT license

Make the next connection