Partition Labels

NeetCode: Partition Labels · LeetCode: 763. Partition Labels · Difficulty: Medium

Split the string s into as many parts as possible so that each letter appears in at most one part. Return the sizes of the parts, in order.

Example

Text

Input:  s = "xyxxyzbzbbisl"    Output: [5, 5, 1, 1, 1]    ("xyxxy", "zbzbb", "i", "s", "l")
Input:  s = "abcabc"          Output: [6]

Brute force: rescan for the last occurrence

A part starting at the first unused character must end at or after that character's last occurrence. Walk forward through the part; for every character, find its last occurrence with String.lastIndexOf, which scans from the end of the string and extend the end if it is farther. When the walk reaches the end, cut the part.

Java

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

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> parts = new ArrayList<>();
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, s.lastIndexOf(s.charAt(i)));
            if (i == end) {
                parts.add(end - start + 1);
                start = i + 1;
            }
        }
        return parts;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.partitionLabels("xyxxyzbzbbisl"));
        System.out.println(sol.partitionLabels("abcabc"));
        System.out.println(sol.partitionLabels(""));
    }
}

Output

[5, 5, 1, 1, 1]
[6]
[]

Time: O(n^2) (each lastIndexOf may scan the string). Space: O(1) besides the output.

Optimal: precompute last indices

The slow step above is finding the last occurrence, which can be precomputed once in a table of 26 slots. s.charAt(i) - 'a' subtracts two char values as int, giving the letter's position from 0 to 25. The string holds lowercase English letters only. A part may not end before the last occurrence of any letter inside it, so end keeps extending; when the index i reaches end, every letter in the part has all its occurrences inside. Cutting there is the earliest safe cut, which gives the most parts.

Java

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> parts = 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) {
                parts.add(end - start + 1);
                start = i + 1;
            }
        }
        return parts;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.partitionLabels("xyxxyzbzbbisl"));
        System.out.println(sol.partitionLabels("abcabc"));
        System.out.println(sol.partitionLabels(""));
    }
}

Output

[5, 5, 1, 1, 1]
[6]
[]

Time: O(n). Space: O(1) (26 counters) besides the output.