Split the string s into as many parts as possible so that each letter appears in at most one part. Return a list of the part sizes. Joined back together, the parts must give s.
s = "ababcbacadefegdehijhklij"[9,7,8] ("ababcbaca", "defegde", "hijhklij")s = "eccbbbbdec"[10]i: end = max(end, last[s[i]]), so the part stretchesi == end: cut ✂️, record end − start + 1, start a new partEvery letter forces an interval from its first to its last appearance, and a part can't cut through any interval. This is Merge Intervals in disguise: end is the right edge of the merged interval so far. Cutting the moment i == end is the earliest legal cut, and cutting early never hurts the rest of the string, so you get the maximum number of parts.
All distinct letters ("abc") → every letter is its own part: [1,1,1]. First letter also last ("abca") → one part covering everything. Remember to return sizes, not the strings. And start = i + 1 after each cut.
Trying every way to cut the string is exponential. What matters is where each letter appears for the last time.
First record the last index of every letter. Scan the string, and stretch the current end to the last index of each letter you see. When i reaches the end, close the part and start a new one.
A part cannot close before the last copy of every letter inside it. Stretch the end, and cut when you reach it.
Run the animation above on your own input, or watch the 1:29 video explanation of Partition Labels with a dry run and Java code.