763. Partition Labels - Explanation

Description

You are given a string s consisting of lowercase english letters.

We want to split the string into as many substrings as possible, while ensuring that each letter appears in at most one substring.

Return a list of integers representing the size of these substrings in the order they appear in the string.

Example 1:

Input: s = "xyxxyzbzbbisl"

Output: [5, 5, 1, 1, 1]

Explanation: The string can be split into ["xyxxy", "zbzbb", "i", "s", "l"].

Example 2:

Input: s = "abcabc"

Output: [6]

Constraints:

1 <= s.length <= 100

Topics

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(m) space, where n is the length of the string s and m is the number of unique characters in the string s.

Hint 1

A character has a first and last index in the given string. Can you think of a greedy approach to solve this problem? Maybe you should try iterating over one of these two indices.

Hint 2

We store the last index of each character in a hash map or an array. As we iterate through the string, treating each index as a potential start of a partition, we track the end of the partition using the maximum last index of the characters seen so far in the current partition. Additionally, we maintain the size of the current partition using a variable, say size.

Hint 3

We update the end of the current partition based on the maximum last index of the characters, extending the partition as needed. When the current index reaches the partition’s end, we finalize the partition, append its size to the output list, reset the size to 0, and continue the same process for the remaining string.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Hash Maps - Used to store and quickly lookup the last occurrence index of each character
Greedy Algorithms - The solution makes locally optimal choices (extending partition to farthest last occurrence) to achieve the global optimum
Two Pointers / Sliding Window - Tracking the current position and the end boundary of each partition

1. Two Pointers (Greedy)

Intuition

We want to split the string into as many parts as possible such that each letter appears in at most one part.

The key observation is:

for any character, we must include all occurrences of that character in the same partition
so if a character appears later in the string, the current partition must extend at least up to that last occurrence

By knowing the last index of every character, we can greedily decide where to end each partition.

As we scan the string:

we keep extending the current partition to the farthest last occurrence of any character seen so far
once we reach that farthest point, the partition can safely end

Algorithm

First, record the last index of every character in the string.
Initialize:
- an empty list res to store partition sizes
- size = 0 for the current partition length
- end = 0 for the farthest index the current partition must reach
Iterate through the string with index i:
For each character c:
- increment the current partition size
- update end = max(end, lastIndex[c])
If i == end:
- we have reached the end of the current partition
- append size to res
- reset size to 0
After processing the whole string, return res

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        lastIndex = {}
        for i, c in enumerate(s):
            lastIndex[c] = i

        res = []
        size = end = 0
        for i, c in enumerate(s):
            size += 1
            end = max(end, lastIndex[c])

            if i == end:
                res.append(size)
                size = 0
        return res

public class Solution {
    public List<Integer> partitionLabels(String s) {
        Map<Character, Integer> lastIndex = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            lastIndex.put(s.charAt(i), i);
        }

        List<Integer> res = new ArrayList<>();
        int size = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            size++;
            end = Math.max(end, lastIndex.get(s.charAt(i)));

            if (i == end) {
                res.add(size);
                size = 0;
            }
        }
        return res;
    }
}

class Solution {
public:
    vector<int> partitionLabels(string s) {
        unordered_map<char, int> lastIndex;
        for (int i = 0; i < s.size(); i++) {
            lastIndex[s[i]] = i;
        }

        vector<int> res;
        int size = 0, end = 0;
        for (int i = 0; i < s.size(); i++) {
            size++;
            end = max(end, lastIndex[s[i]]);

            if (i == end) {
                res.push_back(size);
                size = 0;
            }
        }
        return res;
    }
};

class Solution {
    /**
     * @param {string} S
     * @return {number[]}
     */
    partitionLabels(S) {
        let lastIndex = {};
        for (let i = 0; i < S.length; i++) {
            lastIndex[S[i]] = i;
        }

        let res = [];
        let size = 0,
            end = 0;
        for (let i = 0; i < S.length; i++) {
            size++;
            end = Math.max(end, lastIndex[S[i]]);

            if (i === end) {
                res.push(size);
                size = 0;
            }
        }
        return res;
    }
}

public class Solution {
    public List<int> PartitionLabels(string s) {
        Dictionary<char, int> lastIndex = new Dictionary<char, int>();
        for (int i = 0; i < s.Length; i++) {
            lastIndex[s[i]] = i;
        }

        List<int> res = new List<int>();
        int size = 0, end = 0;
        for (int i = 0; i < s.Length; i++) {
            size++;
            end = Math.Max(end, lastIndex[s[i]]);

            if (i == end) {
                res.Add(size);
                size = 0;
            }
        }
        return res;
    }
}

func partitionLabels(s string) []int {
    lastIndex := make(map[rune]int)
    for i, c := range s {
        lastIndex[c] = i
    }

    var res []int
    size, end := 0, 0
    for i, c := range s {
        size++
        if lastIndex[c] > end {
            end = lastIndex[c]
        }

        if i == end {
            res = append(res, size)
            size = 0
        }
    }
    return res
}

class Solution {
    fun partitionLabels(s: String): List<Int> {
        val lastIndex = HashMap<Char, Int>()
        s.forEachIndexed { i, c -> lastIndex[c] = i }

        val res = mutableListOf<Int>()
        var size = 0
        var end = 0
        for (i in s.indices) {
            size++
            end = maxOf(end, lastIndex[s[i]] ?: 0)

            if (i == end) {
                res.add(size)
                size = 0
            }
        }
        return res
    }
}

class Solution {
    func partitionLabels(_ s: String) -> [Int] {
        var lastIndex = [Character: Int]()
        for (i, c) in s.enumerated() {
            lastIndex[c] = i
        }

        var res = [Int]()
        var size = 0
        var end = 0
        for (i, c) in s.enumerated() {
            size += 1
            end = max(end, lastIndex[c]!)

            if i == end {
                res.append(size)
                size = 0
            }
        }
        return res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(m)$

Where $n$ is the length of the string $s$ and $m$ is the number of unique characters in the string $s$ .

Common Pitfalls

Not Precomputing Last Indices

A common mistake is trying to find the last occurrence of each character on the fly during the main traversal. This leads to O(n^2) time complexity. You must precompute the last index of every character in a first pass to achieve O(n) time.

Forgetting to Reset Partition Size

After completing a partition (when i == end), forgetting to reset the size counter to 0 causes partition sizes to accumulate incorrectly. Each new partition must start with a fresh count.

Off-by-One Errors with Partition Boundaries

When checking if the current index equals the end of the partition, make sure to use the correct comparison. The partition ends when i == end, not i > end or i >= end. An off-by-one error here will either split partitions prematurely or merge partitions that should be separate.