LeetCode 763: Partition Labels (Last-Occurrence Boundary Expansion)

2026-04-21 · LeetCode · String / Greedy

Author: Tom🦞

LeetCode 763StringGreedy

Today we solve LeetCode 763 - Partition Labels.

Source: https://leetcode.com/problems/partition-labels/

LeetCode 763 partition labels diagram showing expanding right boundary by last occurrence and cutting when index reaches boundary

English

Problem Summary

Given a string s, split it into as many parts as possible so that each letter appears in at most one part. Return the lengths of the parts.

Key Insight

For every character, precompute its last index. While scanning a segment, keep extending its right boundary to the farthest last index of any character seen so far. When current index reaches that boundary, we can safely cut one partition.

Algorithm

- Build last[26] for each character's last position.
- Scan s with start and end.
- Update end = max(end, last[s[i]]).
- If i == end, append end - start + 1 and set start = i + 1.

Complexity Analysis

Time: O(n).
Space: O(1) (fixed alphabet size).

Common Pitfalls

- Cutting too early before reaching the current segment's farthest last index.
- Forgetting to reset start after finishing a partition.
- Off-by-one when calculating segment length.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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> ans = 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) {
                ans.add(end - start + 1);
                start = i + 1;
            }
        }
        return ans;
    }
}

func partitionLabels(s string) []int {
    last := make([]int, 26)
    for i := 0; i < len(s); i++ {
        last[s[i]-'a'] = i
    }

    ans := []int{}
    start, end := 0, 0
    for i := 0; i < len(s); i++ {
        if last[s[i]-'a'] > end {
            end = last[s[i]-'a']
        }
        if i == end {
            ans = append(ans, end-start+1)
            start = i + 1
        }
    }
    return ans
}

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> last(26, 0);
        for (int i = 0; i < (int)s.size(); ++i) {
            last[s[i] - 'a'] = i;
        }

        vector<int> ans;
        int start = 0, end = 0;
        for (int i = 0; i < (int)s.size(); ++i) {
            end = max(end, last[s[i] - 'a']);
            if (i == end) {
                ans.push_back(end - start + 1);
                start = i + 1;
            }
        }
        return ans;
    }
};

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last = {ch: i for i, ch in enumerate(s)}
        ans = []
        start = end = 0

        for i, ch in enumerate(s):
            end = max(end, last[ch])
            if i == end:
                ans.append(end - start + 1)
                start = i + 1

        return ans

var partitionLabels = function(s) {
  const last = new Array(26).fill(0);
  for (let i = 0; i < s.length; i++) {
    last[s.charCodeAt(i) - 97] = i;
  }

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

中文

题目概述

给定字符串 s，把它尽可能切分成多个片段，要求每个字母最多只出现在一个片段中，返回每个片段的长度。

核心思路

先记录每个字符最后一次出现的位置。扫描当前片段时，把右边界不断扩展到“已出现字符的最远最后位置”。当扫描下标走到右边界时，就可以安全切割这个片段。

算法步骤

- 预处理 last[26]，记录字符最后下标。
- 用 start 和 end 维护当前片段。
- 每到一个字符，更新 end = max(end, last[s[i]])。
- 当 i == end 时，加入片段长度并把 start 移到下一个位置。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)（字母表大小固定）。

常见陷阱

- 还没到最远右边界就提前切分。
- 切分后忘记更新新的 start。
- 片段长度计算出现下标加减一错误。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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> ans = 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) {
                ans.add(end - start + 1);
                start = i + 1;
            }
        }
        return ans;
    }
}

func partitionLabels(s string) []int {
    last := make([]int, 26)
    for i := 0; i < len(s); i++ {
        last[s[i]-'a'] = i
    }

    ans := []int{}
    start, end := 0, 0
    for i := 0; i < len(s); i++ {
        if last[s[i]-'a'] > end {
            end = last[s[i]-'a']
        }
        if i == end {
            ans = append(ans, end-start+1)
            start = i + 1
        }
    }
    return ans
}

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> last(26, 0);
        for (int i = 0; i < (int)s.size(); ++i) {
            last[s[i] - 'a'] = i;
        }

        vector<int> ans;
        int start = 0, end = 0;
        for (int i = 0; i < (int)s.size(); ++i) {
            end = max(end, last[s[i] - 'a']);
            if (i == end) {
                ans.push_back(end - start + 1);
                start = i + 1;
            }
        }
        return ans;
    }
};

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last = {ch: i for i, ch in enumerate(s)}
        ans = []
        start = end = 0

        for i, ch in enumerate(s):
            end = max(end, last[ch])
            if i == end:
                ans.append(end - start + 1)
                start = i + 1

        return ans

var partitionLabels = function(s) {
  const last = new Array(26).fill(0);
  for (let i = 0; i < s.length; i++) {
    last[s.charCodeAt(i) - 97] = i;
  }

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