Partition Labels

MediumGreedygreedy interval

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given a string s made up of lowercase English letters. Your task is to split s into as many contiguous pieces as possible so that **each letter appears in at most one piece**. In other words, once a given character shows up in a part, that same character may not appear in any other part. The order of the pieces, when concatenated, must reproduce the original string s. Return an array of integers where each value is the length of one part, listed in the order the parts occur in s. You should produce the maximum number of parts that satisfies the rule above. It can be shown that a valid partition into the maximum number of parts is always unique, so there is exactly one correct answer.

Examples

Input: s = "ababcbacadefegdehijhklij"
Output: [9, 7, 8]
The partition is "ababcbaca", "defegde", "hijhklij". Each letter shows up in only one part. A split such as "ababcbaca", "defegde", "hijhkl", "ij" would be invalid because the letters i and j would then span two parts.
Input: s = "eccbbbbdec"
Output: [10]
Both 'e' and 'c' appear near the start and again at the end, forcing the entire string into a single part.
Input: s = "abcdef"
Output: [1, 1, 1, 1, 1, 1]
Every character is unique, so each one can be its own part, giving six parts of length 1.

Constraints

  • `1 <= s.length <= 500`
  • `s` consists of lowercase English letters only (`'a'` through `'z'`).

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More greedy interval problems