DSA-144 · Earliest safe cuts forced by last-occurrence interval closure

Partition Labels

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 3294 deterministic checks. Learner drafts are not executed.

Understand the problem

Partition a lowercase ASCII string into the largest possible number of nonempty contiguous parts such that every distinct character appears in at most one part. Return the lengths of the parts in original order.

text is a non-null String of length 0..100000 containing only ASCII a..z. Null throws NullPointerException; other characters or excessive length throw IllegalArgumentException. Surrogate pairs and other Unicode letters are not silently treated as lowercase ASCII.
Return an immutable List<Integer> of positive lengths summing to text.length(). Empty input returns an empty immutable list. Each character may occur repeatedly within one part, but cannot appear in two different parts.
Maximize the number of parts, rather than minimizing their number or sorting characters. Preserve text order. The earliest safe cuts uniquely determine the maximal decomposition; the reference returns lengths only, not copied substrings.

Examples

Input: text="ababcbacadefegdehijhklij"
Output: [9,7,8]
The first nine characters form one forced closure, then seven, then eight.
Input: text="eccbbbbdec"
Output: [10]
The outer e/c occurrences force the entire string into one part.
Input: text="abc"
Output: [1,1,1]
Every cut is safe when no character repeats.

Before you start

Character indexing and fixed alphabet tables
Intervals and greedy earliest-boundary arguments

Recognize the structure

Every character imposes an interval from its first to last occurrence. A cut inside that interval is forbidden. Scan left to right while expanding the current required end to the greatest last occurrence seen inside the part. Reaching that end closes all encountered character obligations, so cutting immediately preserves as many future boundaries as possible. This is an interval-closure proof, not a frequency threshold.

Try before revealing

Hint 1

What forbids a cut between two occurrences of the same character?

Hint 2

As the current part grows, which encountered character forces the farthest endpoint?

Hint 3

Cut when the scan reaches the maximum last occurrence of everything in the current part.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Test every cut for a character crossing

For each possible cut position, mark the characters to its left and scan its right side for a shared character. Include every safe cut. This O(n²) approach makes the global meaning of a legal boundary explicit; it uses a fixed 26-entry table and O(number of parts) output. The test oracle independently enumerates all short-string segmentations, assigns character ownership to blocks, and selects the decomposition with the most blocks.

Improve the baseline

Record actual final occurrences

Initialize a 26-entry array to −1 and overwrite the entry for every scanned character. The resulting last[ch] is an index, not a count. A validation pass guarantees that char−a is a valid slot before either occurrence scan.

Grow the smallest possible current part

Start a part at start and keep end as the maximum last occurrence of all characters encountered since start. Any legal first part must include that end; newly included positions may introduce other characters that extend it again.

Cut exactly when the scan catches the required end

After updating end with the current character, index==end means no character in the part has an occurrence farther right. Emit index−start+1 and set start=index+1. Delaying this safe cut would merge independent pieces and lose at least one available boundary.

Handle empty and all-equal strings naturally

Empty input never enters the scan and returns an empty list. A repeated single character keeps end at the final index and yields one part. A string of distinct characters closes a part at every position. No zero-length part is emitted.

Separate working memory from output

Only a fixed 26-entry map and two scalar boundaries are algorithm state. The lengths list is output and can have Θ(n) entries under a growing alphabet model; for this fixed 26-letter contract there are at most 26 parts. List.copyOf makes the public result immutable and does not copy text substrings.

Why it is correct

Every emitted part is valid

For every character encountered since start, end is at least its final occurrence. When index reaches end, all occurrences of those characters lie at or before the cut. Earlier closed parts already have no later occurrences, so no character is shared between parts.

The chosen cut is the earliest feasible one

Before index==end, an already encountered character has a later occurrence inside the required closure. Cutting now would split that character between parts. Thus every valid partition must keep the whole greedy first part together.

Optimality repeats on the suffix

The earliest safe cut separates disjoint character sets. Any valid partition that delays it can be refined by adding this cut without affecting validity, increasing or preserving its number of parts. Apply the same argument to the remaining suffix. Every optimum therefore contains all greedy boundaries, proving maximality and uniqueness. The finite scan preserves input order.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;

public final class Solution {
    private Solution() {}
    private static void validate(String text) {
        Objects.requireNonNull(text, "text");
        if (text.length() > 100_000) throw new IllegalArgumentException("too long");
        for (int index = 0; index < text.length(); index++) {
            char ch = text.charAt(index);
            if (ch < 'a' || ch > 'z') throw new IllegalArgumentException("ASCII lowercase required");
        }
    }
    public static List<Integer> partitionLabels(String text) {
        validate(text);
        int[] last = new int[26];
        Arrays.fill(last, -1);
        for (int index = 0; index < text.length(); index++) last[text.charAt(index) - 'a'] = index;
        List<Integer> lengths = new ArrayList<>();
        int start = 0, end = -1;
        for (int index = 0; index < text.length(); index++) {
            end = Math.max(end, last[text.charAt(index) - 'a']);
            if (index == end) {
                lengths.add(index - start + 1);
                start = index + 1;
            }
        }
        return List.copyOf(lengths);
    }
    // Check every possible cut by scanning left and right; short inputs only.
    public static List<Integer> baseline(String text) {
        validate(text);
        List<Integer> lengths = new ArrayList<>();
        int start = 0;
        for (int cut = 1; cut <= text.length(); cut++) {
            boolean[] left = new boolean[26];
            for (int i = 0; i < cut; i++) left[text.charAt(i) - 'a'] = true;
            boolean safe = true;
            for (int i = cut; i < text.length(); i++) if (left[text.charAt(i) - 'a']) safe = false;
            if (safe) {
                lengths.add(cut - start);
                start = cut;
            }
        }
        return List.copyOf(lengths);
    }
}

Read the meaningful blocks

Validate the exact alphabet

Character.isLowerCase accepts characters beyond a..z and would not justify a 26-slot array. Explicit range checks keep the data representation and contract aligned.

Update the closure before checking for a cut

The current character may force a farther last occurrence. Checking index==end first would prematurely close the part containing that character.

Emit a length and advance the next start

Indices are zero-based while lengths count both endpoints, hence index−start+1. start advances only after an emitted boundary, and List.copyOf exposes a stable immutable value.

Complexity

Validation, final-occurrence collection, and closure scanning each take O(n) time. Working space is O(26)=O(1). Including the returned list takes O(p) additional entries, where p is the number of parts and p≤min(n,26) for this alphabet.

The cut-testing baseline takes O(n²) time and O(26+p) space including output. A generalized alphabet would need a map of distinct symbols and explicit Unicode code-point versus UTF-16 indexing semantics; those costs and units are outside this ASCII contract.

Exact-state walkthroughs

Reveal normal and boundary traces

A later character extends the current closure

Input: "abacbdde" · Maximal partition lengths: [5,2,1]

Step 1 of 14: Record the final index of every present ASCII character.

These are positions, not frequencies. Only the fixed alphabet table is reference workspace; displayed maps omit unused slots.

Partition Labels — close every character obligation

Phase: initial.

Final character occurrence indices

a: 2
b: 4
c: 3
d: 6
e: 7

Next/current part starts at 0; required last-occurrence end is -1.

0: afuture input
1: bfuture input
2: afuture input
3: cfuture input
4: bfuture input
5: dfuture input
6: dfuture input
7: efuture input

Emitted lengths in original order

Empty.

Every safe cut is chosen as soon as all encountered characters finish. ASCII character indices and lengths use the same units. Empty input yields an empty immutable list.

State after this step
Variable	Value
input	`"abacbdde"`
phase	`"initial"`
last	`{"a":2,"b":4,"c":3,"d":6,"e":7}`
start	`0`
end	`-1`
lengths	`[]`

See the affected Java block

 1 import java.util.ArrayList;
 2 import java.util.Arrays;
 3 import java.util.List;
 4 import java.util.Objects;
 5 
 6 public final class Solution {
 7     private Solution() {}
 8     private static void validate(String text) {
 9         Objects.requireNonNull(text, "text");
10         if (text.length() > 100_000) throw new IllegalArgumentException("too long");
11         for (int index = 0; index < text.length(); index++) {
12             char ch = text.charAt(index);
13             if (ch < 'a' || ch > 'z') throw new IllegalArgumentException("ASCII lowercase required");
14         }
15     }
16     public static List<Integer> partitionLabels(String text) {
17         validate(text);
18         int[] last = new int[26];
19         Arrays.fill(last, -1);
20         for (int index = 0; index < text.length(); index++) last[text.charAt(index) - 'a'] = index;
21         List<Integer> lengths = new ArrayList<>();
22         int start = 0, end = -1;
23         for (int index = 0; index < text.length(); index++) {
24             end = Math.max(end, last[text.charAt(index) - 'a']);
25             if (index == end) {
26                 lengths.add(index - start + 1);
27                 start = index + 1;
28             }
29         }
30         return List.copyOf(lengths);
31     }
32     // Check every possible cut by scanning left and right; short inputs only.
33     public static List<Integer> baseline(String text) {
34         validate(text);
35         List<Integer> lengths = new ArrayList<>();
36         int start = 0;
37         for (int cut = 1; cut <= text.length(); cut++) {
38             boolean[] left = new boolean[26];
39             for (int i = 0; i < cut; i++) left[text.charAt(i) - 'a'] = true;
40             boolean safe = true;
41             for (int i = cut; i < text.length(); i++) if (left[text.charAt(i) - 'a']) safe = false;
42             if (safe) {
43                 lengths.add(cut - start);
44                 start = cut;
45             }
46         }
47         return List.copyOf(lengths);
48     }
49 }
50

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Record the final index of every present ASCII character.
These are positions, not frequencies. Only the fixed alphabet table is reference workspace; displayed maps omit unused slots.
input
"abacbdde"
phase
"initial"
last
{"a":2,"b":4,"c":3,"d":6,"e":7}
start
0
end
-1
lengths
[]
Include this character’s entire occurrence obligation.
Every legal cut must lie at or beyond every last occurrence already encountered in this part.
input
"abacbdde"
phase
"extend"
last
{"a":2,"b":4,"c":3,"d":6,"e":7}
start
0
end
2
lengths
[]
index
0
character
"a"
previousEnd
-1
Include this character’s entire occurrence obligation.
Every legal cut must lie at or beyond every last occurrence already encountered in this part.
input
"abacbdde"
phase
"extend"
last
{"a":2,"b":4,"c":3,"d":6,"e":7}
start
0
end
4
lengths
[]
index
1
character
"b"
previousEnd
2
Include this character’s entire occurrence obligation.
Every legal cut must lie at or beyond every last occurrence already encountered in this part.
input
"abacbdde"
phase
"extend"
last
{"a":2,"b":4,"c":3,"d":6,"e":7}
start
0
end
4
lengths
[]
index
2
character
"a"
previousEnd
4
Include this character’s entire occurrence obligation.
Every legal cut must lie at or beyond every last occurrence already encountered in this part.
input
"abacbdde"
phase
"extend"
last
{"a":2,"b":4,"c":3,"d":6,"e":7}
start
0
end
4
lengths
[]
index
3
character
"c"
previousEnd
4
Include this character’s entire occurrence obligation.
Every legal cut must lie at or beyond every last occurrence already encountered in this part.
input
"abacbdde"
phase
"extend"
last
{"a":2,"b":4,"c":3,"d":6,"e":7}
start
0
end
4
lengths
[]
index
4
character
"b"
previousEnd
4
Emit the earliest safe part and start the remaining suffix.
All characters of the closed part finish here or earlier. No earlier cut was legal; delaying a safe cut loses an available part.
input
"abacbdde"
phase
"cut"
last
{"a":2,"b":4,"c":3,"d":6,"e":7}
start
5
end
4
lengths
[5]
index
4
cutStart
0
Include this character’s entire occurrence obligation.
Every legal cut must lie at or beyond every last occurrence already encountered in this part.
input
"abacbdde"
phase
"extend"
last
{"a":2,"b":4,"c":3,"d":6,"e":7}
start
5
end
6
lengths
[5]
index
5
character
"d"
previousEnd
4
Include this character’s entire occurrence obligation.
Every legal cut must lie at or beyond every last occurrence already encountered in this part.
input
"abacbdde"
phase
"extend"
last
{"a":2,"b":4,"c":3,"d":6,"e":7}
start
5
end
6
lengths
[5]
index
6
character
"d"
previousEnd
6
Emit the earliest safe part and start the remaining suffix.
All characters of the closed part finish here or earlier. No earlier cut was legal; delaying a safe cut loses an available part.
input
"abacbdde"
phase
"cut"
last
{"a":2,"b":4,"c":3,"d":6,"e":7}
start
7
end
6
lengths
[5,2]
index
6
cutStart
5
Include this character’s entire occurrence obligation.
Every legal cut must lie at or beyond every last occurrence already encountered in this part.
input
"abacbdde"
phase
"extend"
last
{"a":2,"b":4,"c":3,"d":6,"e":7}
start
7
end
7
lengths
[5,2]
index
7
character
"e"
previousEnd
6
Emit the earliest safe part and start the remaining suffix.
All characters of the closed part finish here or earlier. No earlier cut was legal; delaying a safe cut loses an available part.
input
"abacbdde"
phase
"cut"
last
{"a":2,"b":4,"c":3,"d":6,"e":7}
start
8
end
7
lengths
[5,2,1]
index
7
cutStart
7
Return immutable lengths in original order.
Lengths sum to the input length, with no shared character across parts. Empty text emits no parts.
input
"abacbdde"
phase
"complete"
last
{"a":2,"b":4,"c":3,"d":6,"e":7}
start
8
end
7
lengths
[5,2,1]
Return the documented outcome.
The result follows the stated empty, failure, and mutation contract. Histories and original occurrence cards are teaching data rather than reference workspace.
result
[5,2,1]

All characters are independent

Input: "abc" · Maximal partition lengths: [1,1,1]

Step 1 of 9: Record the final index of every present ASCII character.

These are positions, not frequencies. Only the fixed alphabet table is reference workspace; displayed maps omit unused slots.

Partition Labels — close every character obligation

Phase: initial.

Final character occurrence indices

a: 0
b: 1
c: 2

Next/current part starts at 0; required last-occurrence end is -1.

0: afuture input
1: bfuture input
2: cfuture input

Emitted lengths in original order

Empty.

Every safe cut is chosen as soon as all encountered characters finish. ASCII character indices and lengths use the same units. Empty input yields an empty immutable list.

State after this step
Variable	Value
input	`"abc"`
phase	`"initial"`
last	`{"a":0,"b":1,"c":2}`
start	`0`
end	`-1`
lengths	`[]`

See the affected Java block

 1 import java.util.ArrayList;
 2 import java.util.Arrays;
 3 import java.util.List;
 4 import java.util.Objects;
 5 
 6 public final class Solution {
 7     private Solution() {}
 8     private static void validate(String text) {
 9         Objects.requireNonNull(text, "text");
10         if (text.length() > 100_000) throw new IllegalArgumentException("too long");
11         for (int index = 0; index < text.length(); index++) {
12             char ch = text.charAt(index);
13             if (ch < 'a' || ch > 'z') throw new IllegalArgumentException("ASCII lowercase required");
14         }
15     }
16     public static List<Integer> partitionLabels(String text) {
17         validate(text);
18         int[] last = new int[26];
19         Arrays.fill(last, -1);
20         for (int index = 0; index < text.length(); index++) last[text.charAt(index) - 'a'] = index;
21         List<Integer> lengths = new ArrayList<>();
22         int start = 0, end = -1;
23         for (int index = 0; index < text.length(); index++) {
24             end = Math.max(end, last[text.charAt(index) - 'a']);
25             if (index == end) {
26                 lengths.add(index - start + 1);
27                 start = index + 1;
28             }
29         }
30         return List.copyOf(lengths);
31     }
32     // Check every possible cut by scanning left and right; short inputs only.
33     public static List<Integer> baseline(String text) {
34         validate(text);
35         List<Integer> lengths = new ArrayList<>();
36         int start = 0;
37         for (int cut = 1; cut <= text.length(); cut++) {
38             boolean[] left = new boolean[26];
39             for (int i = 0; i < cut; i++) left[text.charAt(i) - 'a'] = true;
40             boolean safe = true;
41             for (int i = cut; i < text.length(); i++) if (left[text.charAt(i) - 'a']) safe = false;
42             if (safe) {
43                 lengths.add(cut - start);
44                 start = cut;
45             }
46         }
47         return List.copyOf(lengths);
48     }
49 }
50

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Record the final index of every present ASCII character.
These are positions, not frequencies. Only the fixed alphabet table is reference workspace; displayed maps omit unused slots.
input
"abc"
phase
"initial"
last
{"a":0,"b":1,"c":2}
start
0
end
-1
lengths
[]
Include this character’s entire occurrence obligation.
Every legal cut must lie at or beyond every last occurrence already encountered in this part.
input
"abc"
phase
"extend"
last
{"a":0,"b":1,"c":2}
start
0
end
0
lengths
[]
index
0
character
"a"
previousEnd
-1
Emit the earliest safe part and start the remaining suffix.
All characters of the closed part finish here or earlier. No earlier cut was legal; delaying a safe cut loses an available part.
input
"abc"
phase
"cut"
last
{"a":0,"b":1,"c":2}
start
1
end
0
lengths
[1]
index
0
cutStart
0
Include this character’s entire occurrence obligation.
Every legal cut must lie at or beyond every last occurrence already encountered in this part.
input
"abc"
phase
"extend"
last
{"a":0,"b":1,"c":2}
start
1
end
1
lengths
[1]
index
1
character
"b"
previousEnd
0
Emit the earliest safe part and start the remaining suffix.
All characters of the closed part finish here or earlier. No earlier cut was legal; delaying a safe cut loses an available part.
input
"abc"
phase
"cut"
last
{"a":0,"b":1,"c":2}
start
2
end
1
lengths
[1,1]
index
1
cutStart
1
Include this character’s entire occurrence obligation.
Every legal cut must lie at or beyond every last occurrence already encountered in this part.
input
"abc"
phase
"extend"
last
{"a":0,"b":1,"c":2}
start
2
end
2
lengths
[1,1]
index
2
character
"c"
previousEnd
1
Emit the earliest safe part and start the remaining suffix.
All characters of the closed part finish here or earlier. No earlier cut was legal; delaying a safe cut loses an available part.
input
"abc"
phase
"cut"
last
{"a":0,"b":1,"c":2}
start
3
end
2
lengths
[1,1,1]
index
2
cutStart
2
Return immutable lengths in original order.
Lengths sum to the input length, with no shared character across parts. Empty text emits no parts.
input
"abc"
phase
"complete"
last
{"a":0,"b":1,"c":2}
start
3
end
2
lengths
[1,1,1]
Return the documented outcome.
The result follows the stated empty, failure, and mutation contract. Histories and original occurrence cards are teaching data rather than reference workspace.
result
[1,1,1]

One character spans the entire input

Input: "aaaa" · Maximal partition lengths: [4]

Step 1 of 8: Record the final index of every present ASCII character.

These are positions, not frequencies. Only the fixed alphabet table is reference workspace; displayed maps omit unused slots.

Partition Labels — close every character obligation

Phase: initial.

Final character occurrence indices

a: 3

Next/current part starts at 0; required last-occurrence end is -1.

0: afuture input
1: afuture input
2: afuture input
3: afuture input

Emitted lengths in original order

Empty.

Every safe cut is chosen as soon as all encountered characters finish. ASCII character indices and lengths use the same units. Empty input yields an empty immutable list.

State after this step
Variable	Value
input	`"aaaa"`
phase	`"initial"`
last	`{"a":3}`
start	`0`
end	`-1`
lengths	`[]`

See the affected Java block

 1 import java.util.ArrayList;
 2 import java.util.Arrays;
 3 import java.util.List;
 4 import java.util.Objects;
 5 
 6 public final class Solution {
 7     private Solution() {}
 8     private static void validate(String text) {
 9         Objects.requireNonNull(text, "text");
10         if (text.length() > 100_000) throw new IllegalArgumentException("too long");
11         for (int index = 0; index < text.length(); index++) {
12             char ch = text.charAt(index);
13             if (ch < 'a' || ch > 'z') throw new IllegalArgumentException("ASCII lowercase required");
14         }
15     }
16     public static List<Integer> partitionLabels(String text) {
17         validate(text);
18         int[] last = new int[26];
19         Arrays.fill(last, -1);
20         for (int index = 0; index < text.length(); index++) last[text.charAt(index) - 'a'] = index;
21         List<Integer> lengths = new ArrayList<>();
22         int start = 0, end = -1;
23         for (int index = 0; index < text.length(); index++) {
24             end = Math.max(end, last[text.charAt(index) - 'a']);
25             if (index == end) {
26                 lengths.add(index - start + 1);
27                 start = index + 1;
28             }
29         }
30         return List.copyOf(lengths);
31     }
32     // Check every possible cut by scanning left and right; short inputs only.
33     public static List<Integer> baseline(String text) {
34         validate(text);
35         List<Integer> lengths = new ArrayList<>();
36         int start = 0;
37         for (int cut = 1; cut <= text.length(); cut++) {
38             boolean[] left = new boolean[26];
39             for (int i = 0; i < cut; i++) left[text.charAt(i) - 'a'] = true;
40             boolean safe = true;
41             for (int i = cut; i < text.length(); i++) if (left[text.charAt(i) - 'a']) safe = false;
42             if (safe) {
43                 lengths.add(cut - start);
44                 start = cut;
45             }
46         }
47         return List.copyOf(lengths);
48     }
49 }
50

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Record the final index of every present ASCII character.
These are positions, not frequencies. Only the fixed alphabet table is reference workspace; displayed maps omit unused slots.
input
"aaaa"
phase
"initial"
last
{"a":3}
start
0
end
-1
lengths
[]
Include this character’s entire occurrence obligation.
Every legal cut must lie at or beyond every last occurrence already encountered in this part.
input
"aaaa"
phase
"extend"
last
{"a":3}
start
0
end
3
lengths
[]
index
0
character
"a"
previousEnd
-1
Include this character’s entire occurrence obligation.
Every legal cut must lie at or beyond every last occurrence already encountered in this part.
input
"aaaa"
phase
"extend"
last
{"a":3}
start
0
end
3
lengths
[]
index
1
character
"a"
previousEnd
3
Include this character’s entire occurrence obligation.
Every legal cut must lie at or beyond every last occurrence already encountered in this part.
input
"aaaa"
phase
"extend"
last
{"a":3}
start
0
end
3
lengths
[]
index
2
character
"a"
previousEnd
3
Include this character’s entire occurrence obligation.
Every legal cut must lie at or beyond every last occurrence already encountered in this part.
input
"aaaa"
phase
"extend"
last
{"a":3}
start
0
end
3
lengths
[]
index
3
character
"a"
previousEnd
3
Emit the earliest safe part and start the remaining suffix.
All characters of the closed part finish here or earlier. No earlier cut was legal; delaying a safe cut loses an available part.
input
"aaaa"
phase
"cut"
last
{"a":3}
start
4
end
3
lengths
[4]
index
3
cutStart
0
Return immutable lengths in original order.
Lengths sum to the input length, with no shared character across parts. Empty text emits no parts.
input
"aaaa"
phase
"complete"
last
{"a":3}
start
4
end
3
lengths
[4]
Return the documented outcome.
The result follows the stated empty, failure, and mutation contract. Histories and original occurrence cards are teaching data rather than reference workspace.
result
[4]

No parts

Input: "" · Maximal partition lengths: []

Step 1 of 3: Record the final index of every present ASCII character.

These are positions, not frequencies. Only the fixed alphabet table is reference workspace; displayed maps omit unused slots.

Partition Labels — close every character obligation

Phase: initial.

Final character occurrence indices

Empty.

Next/current part starts at 0; required last-occurrence end is -1.

Emitted lengths in original order

Empty.

Every safe cut is chosen as soon as all encountered characters finish. ASCII character indices and lengths use the same units. Empty input yields an empty immutable list.

State after this step
Variable	Value
input	`""`
phase	`"initial"`
last	`{}`
start	`0`
end	`-1`
lengths	`[]`

See the affected Java block

 1 import java.util.ArrayList;
 2 import java.util.Arrays;
 3 import java.util.List;
 4 import java.util.Objects;
 5 
 6 public final class Solution {
 7     private Solution() {}
 8     private static void validate(String text) {
 9         Objects.requireNonNull(text, "text");
10         if (text.length() > 100_000) throw new IllegalArgumentException("too long");
11         for (int index = 0; index < text.length(); index++) {
12             char ch = text.charAt(index);
13             if (ch < 'a' || ch > 'z') throw new IllegalArgumentException("ASCII lowercase required");
14         }
15     }
16     public static List<Integer> partitionLabels(String text) {
17         validate(text);
18         int[] last = new int[26];
19         Arrays.fill(last, -1);
20         for (int index = 0; index < text.length(); index++) last[text.charAt(index) - 'a'] = index;
21         List<Integer> lengths = new ArrayList<>();
22         int start = 0, end = -1;
23         for (int index = 0; index < text.length(); index++) {
24             end = Math.max(end, last[text.charAt(index) - 'a']);
25             if (index == end) {
26                 lengths.add(index - start + 1);
27                 start = index + 1;
28             }
29         }
30         return List.copyOf(lengths);
31     }
32     // Check every possible cut by scanning left and right; short inputs only.
33     public static List<Integer> baseline(String text) {
34         validate(text);
35         List<Integer> lengths = new ArrayList<>();
36         int start = 0;
37         for (int cut = 1; cut <= text.length(); cut++) {
38             boolean[] left = new boolean[26];
39             for (int i = 0; i < cut; i++) left[text.charAt(i) - 'a'] = true;
40             boolean safe = true;
41             for (int i = cut; i < text.length(); i++) if (left[text.charAt(i) - 'a']) safe = false;
42             if (safe) {
43                 lengths.add(cut - start);
44                 start = cut;
45             }
46         }
47         return List.copyOf(lengths);
48     }
49 }
50

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Record the final index of every present ASCII character.
These are positions, not frequencies. Only the fixed alphabet table is reference workspace; displayed maps omit unused slots.
input
""
phase
"initial"
last
{}
start
0
end
-1
lengths
[]
Return immutable lengths in original order.
Lengths sum to the input length, with no shared character across parts. Empty text emits no parts.
input
""
phase
"complete"
last
{}
start
0
end
-1
lengths
[]
Return the documented outcome.
The result follows the stated empty, failure, and mutation contract. Histories and original occurrence cards are teaching data rather than reference workspace.
result
[]

Test the contract

Input: text=""
Output: []
No nonempty parts.
Input: text="aaaa"
Output: [4]
One character forces one part.
Input: text="abac"
Output: [3,1]
a forces the first closure; c is independent.
Input: text="abca"
Output: [4]
The closing a forbids every interior cut.
Input: text="abc"
Output: [1,1,1]
Three independent characters.
Input: text="aA"
Output: IllegalArgumentException
Uppercase is outside the contract.

Common mistakes and counterexamples

Cut after a character reaches its own last occurrence

Counterexample: In "abac", the first a closure includes b; in more interleaved strings b can extend it further.

Track the maximum last index of every character in the growing part.

Count frequencies instead of final positions

Counterexample: Knowing a appears twice does not reveal where a safe boundary lies.

Use last occurrence indices to describe crossing obligations.

Return substring lengths without maximizing part count

Counterexample: The whole nonempty string is always valid but need not be optimal.

Cut at every earliest safe closure.

Use lowercase Unicode predicates for a 26-slot table

Counterexample: "é" is lowercase but is not an ASCII slot.

Validate a..z explicitly before indexing.

Follow-ups

Return index ranges or substring views.

Emit [start,end] at the same safe boundaries and define inclusive versus exclusive endpoints. Creating copied substrings adds output-character storage, whereas ranges keep only O(p) index pairs.

Support general Unicode.

Choose code points, grapheme clusters, or UTF-16 units before implementing. Use a map for last occurrences and express returned lengths in that same chosen unit; a 26-slot table is then inappropriate.

Process a stream without seeing future input.

A prefix alone cannot prove a character has no later occurrence. Exact final partitions require future knowledge, a second pass over retained input, or a promise about symbol completion. The current last-occurrence proof explains this limitation.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 143/20,000 characters

Self-review

I can define end as an obligation maximum rather than a character frequency.I can prove validity, earliest-cut necessity, and optimality separately.I can state output length units, immutable result behavior, and the fixed-alphabet space bound.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Greedy reasoning: justify compressed choices

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-18 · Original teaching content and implementations authored for AceYourInterviews. Familiar interview problem names describe standard algorithmic tasks; no company-frequency or platform-difficulty claims are made.