Skip to main content

23. Partition Labels

mediumAsked at Databricks

Greedily partition a string so each character appears in exactly one part — a range-merging pattern Databricks reuses when computing non-overlapping file-range compaction windows in Delta Lake's OPTIMIZE command.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

You are given a string s. Partition it into as many parts as possible so that each letter appears in at most one part. Return a list of the sizes of these parts.

Constraints

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

Examples

Example 1

Input
s = "ababcbacadefegdehijhklij"
Output
[9,7,8]

Explanation: Parts are "ababcbaca" (9), "defegde" (7), "hijhklij" (8). Each letter lives in only one part.

Example 2

Input
s = "eccbbbbdec"
Output
[10]

Approaches

1. Greedy with last-occurrence map

Record the last index of each character. Walk the string, extending the current partition end to the furthest last-occurrence seen so far. When the pointer reaches the current end, record the partition size and start a new one.

Time
O(n)
Space
O(1)
function partitionLabels(s) {
  const last = {};
  for (let i = 0; i < s.length; i++) last[s[i]] = i;

  const result = [];
  let start = 0, end = 0;
  for (let i = 0; i < s.length; i++) {
    end = Math.max(end, last[s[i]]);
    if (i === end) {
      result.push(end - start + 1);
      start = i + 1;
    }
  }
  return result;
}

Tradeoff:

Databricks-specific tips

Databricks interviewers appreciate when you frame this as an interval-merging problem: each character defines an interval [firstOccurrence, lastOccurrence], and the task is to merge overlapping intervals into minimal non-overlapping ranges. That framing translates word-for-word into how Delta's file-range compaction decides which data files to co-compact. Mention interval merge explicitly — it signals you see the general pattern, not just the string-specific trick.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

More Databricks coding interview questions

See all Databricks problems →

Companies that also ask Partition Labels