Partition Labels

Medium Intervals Basics Original on LeetCode

Reported atBarclaysInMobi

Partition Labels is a medium intervals problem solved with the basics pattern. The best approach, optimal (last-index table + greedy cut), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (rescan for last occurrences) up.

Problem

You are given a string s of lowercase letters. Cut it into as many contiguous parts as possible such that each letter appears in at most one part.

Return a list with the length of every part, from left to right. Concatenating the parts in order must give back s.

Examples

Example 1

Input
s = "abacdcefge"
Output
[3, 3, 4]
Why
Parts "aba", "cdc" and "efge": every letter lives in exactly one part, and no part can be split further.

Example 2

Input
s = "xyz"
Output
[1, 1, 1]
Why
All letters are different, so each one can be its own part.

Example 3

Input
s = "mnopm"
Output
[5]
Why
'm' appears at both ends, so the whole string must stay together.

Constraints

  • 1 <= s.length <= 500
  • s consists only of lowercase English letters

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (rescan for last occurrences)O(n²)O(1)
Optimal (last-index table + greedy cut)O(n)O(1)

1Brute force (rescan for last occurrences)

TimeO(n²)Each of the n positions may scan the string from the right to find its last occurrence.
SpaceO(1)Only a few indices besides the output.

Start a part at index start. Keep an end pointer; for every index i inside the part, scan the rest of the string to find the last occurrence of s[i] and push end out to it. When i passes end, the part is closed and the next one starts.

  1. start = 0.
  2. While start < n: end = start; for i from start while i <= end: find the last index of s[i] by scanning from the right, end = max(end, that index).
  3. Record end - start + 1 and set start = end + 1.
  4. Return the recorded sizes.
class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> sizes = new ArrayList<>();
        int n = s.length(), start = 0;
        while (start < n) {
            int end = start;
            for (int i = start; i <= end; i++) {
                int last = n - 1;
                while (s.charAt(last) != s.charAt(i)) last--;
                end = Math.max(end, last);
            }
            sizes.add(end - start + 1);
            start = end + 1;
        }
        return sizes;
    }
}

2Optimal (last-index table + greedy cut)

TimeO(n)Two linear passes over the string.
SpaceO(1)A fixed array of 26 indices (output not counted).

Record the last index of each of the 26 letters in one pass. Then scan again, stretching the current part's end to last[s[i]] for every letter seen. When i == end, every letter of the part has had its final appearance, so this is the earliest legal cut; cutting as early as possible yields the most parts.

  1. last[c] = the largest index of letter c.
  2. start = 0, end = 0.
  3. For i in 0..n-1: end = max(end, last[s[i]]); if i == end, record i - start + 1 and set start = i + 1.
  4. Return the recorded sizes.
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> sizes = 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) {
                sizes.add(i - start + 1);
                start = i + 1;
            }
        }
        return sizes;
    }
}

Edge cases to test

  • A single character
  • All characters the same
  • All characters distinct (every part has length 1)
  • The first and last characters are equal (one part)

Hints

Hint 1

Once a letter appears in a part, the part must reach at least that letter's last occurrence.

Hint 2

Precompute the last index of every letter.

Hint 3

Walk left to right, extending the current part's end to the last index of each letter you meet; when your position reaches that end, close the part.

FAQ

What is the best time complexity for Partition Labels?

Optimal (last-index table + greedy cut) runs in O(n) time and O(1) extra space. Two linear passes over the string.

Which pattern does Partition Labels use?

It is a intervals problem that uses the basics pattern. Other problems with the same pattern: Detect overlap unsorted, Detect overlap sorted intervals, Interval List Intersections.

Is there a brute force solution for Partition Labels?

Yes. Brute force (rescan for last occurrences) takes O(n²) time and O(1) space. Start a part at index start.

Which edge cases should I test for Partition Labels?

A single character; All characters the same; All characters distinct (every part has length 1); The first and last characters are equal (one part).