Partition labels with last occurrences

Why this matters

Imagine a shop that packs items into boxes. Each item has a label with a letter on it. The rule is strict: all items with the same letter must go in the same box. The shop wants as many boxes as possible.

This is a small version of a common problem. You read a list of items from left to right and must decide where each box ends. A greedy algorithm is a method that makes the best choice it can see right now and never goes back to change it. For this problem the greedy choice is easy to see once you know where each letter last appears.

This lesson solves the problem with two passes over the string. The first pass records the last position of every letter. The second pass cuts the string into pieces as early as it safely can. The lesson on merging intervals works with ranges in a similar way. This lesson only needs the C++ ideas of std::string_view, std::array and std::vector, which are explained where they are used.

The problem in plain words

You are given a string such as abac. Cut it into consecutive pieces. Every piece is a substring, which means a run of letters taken from one place in the string with no gaps. The rule is that a letter may appear in only one piece. Find the cuts that give the most pieces, and return the length of each piece in order.

Take abac first. Number the positions from zero: a is at 0, b at 1, a at 2, and c at 3. The two a letters are at positions 0 and 2, so every cut must keep both of them in the same piece. The string can be cut as aba and c, which gives two pieces with lengths 3 and 1. The cut a and bac is not allowed, because the letter a would then be in two pieces.

The answer for abac is [3, 1]. Here [3, 1] is a list of two numbers, written the way the program later in this lesson prints a std::vector.

Now take a longer string, ababcbacadefegdehijhklij. Its answer is [9, 7, 8]. The first piece is ababcbaca, which has nine letters. The second piece is defegde, with seven letters. The third piece is hijhklij, with eight letters. You can check each piece: no letter from the first piece appears in the second or third piece, and the same holds for the other pairs.

The idea in two steps

The problem looks hard at first, because a cut in one place may force a cut somewhere else. The key fact is this. Every letter occupies a span, from its first position to its last position. A piece is valid only if it contains whole spans. A piece can end at position i only if no letter that starts at or before i also ends after i.

The solution works in two steps.

Step 1 is to record, for each letter, the last position where it appears. For abac, the letter a last appears at 2, the letter b last appears at 1, and the letter c last appears at 3. Here is the table.

Step 2 is to walk the string from left to right and keep one number called reach. The number reach is the furthest last position of any letter seen so far in the current piece. At each position i, update reach with the last position of the letter at i. If i is equal to reach, the scan has caught up with every letter it has opened. Cut the piece here, and start a new piece at i + 1.

Worked example: abac

Start with reach equal to 0 and an empty list of pieces.

• At i = 0, the letter is a, whose last position is 2. reach becomes 2. Since i is not 2, do not cut.
• At i = 1, the letter is b, whose last position is 1. reach stays 2, because the maximum of 2 and 1 is 2. Do not cut.
• At i = 2, the letter is a, whose last position is 2. reach stays 2. Now i equals reach. Cut. The piece runs from position 0 to position 2, so its length is 2 - 0 + 1 = 3. The next piece starts at position 3.
• At i = 3, the letter is c, whose last position is 3. reach becomes 3. Now i equals reach. Cut. The piece runs from position 3 to position 3, so its length is 1.

The answer is [3, 1]. The cut after position 2 is the earliest point where the first piece can end. A cut after position 1 would split the two a letters.

Writing it in C++

Here is the trace above written as C++ code. The function takes a std::string_view. A string view is a light object that points at characters that already exist, so the function does not copy the string. The code uses std::array<int, 26> to hold the last position of each lowercase letter. The letter a is stored at index 0, b at index 1, and so on. The expression s[i] - 'a' turns a letter into its index.

#include <algorithm>
#include <array>
#include <iostream>
#include <string>
#include <string_view>
#include <vector>
 
std::vector<int> partitionLabels(std::string_view s) {
    const int n = static_cast<int>(s.size());
 
    std::array<int, 26> last{};
    last.fill(-1);
    for (int i = 0; i < n; ++i) {
        last[s[i] - 'a'] = i;
    }
 
    std::vector<int> sizes;
    int start = 0;  // first index of the current piece
    int reach = 0;  // furthest last position of any letter seen in this piece
    for (int i = 0; i < n; ++i) {
        reach = std::max(reach, last[s[i] - 'a']);
        if (i == reach) {
            sizes.push_back(i - start + 1);
            start = i + 1;
        }
    }
    return sizes;
}
 
void print(const std::vector<int>& v) {
    std::cout << '[';
    for (std::size_t i = 0; i < v.size(); ++i) {
        if (i) std::cout << ", ";
        std::cout << v[i];
    }
    std::cout << "]\n";
}
 
int main() {
    for (std::string_view s : {"ababcbacadefegdehijhklij", "abac", "eccbbbbdec", "abcabcdd", "a", "zz"}) {
        std::cout << s << " -> ";
        print(partitionLabels(s));
    }
}

Compile it with the standard flags and run it.

g++ -std=c++20 -Wall -Wextra -o partition partition.cpp
./partition

The output is:

ababcbacadefegdehijhklij -> [9, 7, 8]
abac -> [3, 1]
eccbbbbdec -> [10]
abcabcdd -> [6, 2]
a -> [1]
zz -> [2]

The program compiles with no warnings, even with -Wextra turned on.

Two details in the code matter. First, last.fill(-1) sets every letter to -1 before the first pass. Only letters that appear in the string are ever read, so the value -1 is never used. Setting it anyway makes a letter that never appears easy to recognise if you print the table while debugging. Second, the variable start is updated only at a cut. The size of a piece is always i - start + 1, which counts both ends.

A second example: one piece

Take eccbbbbdec. The positions are numbered from zero: e at 0, c at 1 and 2, b at 3 to 6, d at 7, e at 8, and c at 9. The last e is at 8, the last c is at 9, the last b is at 6, and the last d is at 7.

At i = 0 the letter e sets reach to 8. At i = 1 the letter c has a last position of 9, so reach jumps to 9. From then on reach stays at 9, and no index before 9 can equal it. The scan cuts only at i = 9, so the string is one piece of length 10. The answer is [10].

This case teaches a point about reading the trace. A cut happens only when i equals reach. If reach is larger than i, some letter opened in the piece still appears further on, so the piece must continue.

A third example: two blocks that touch

Take abcabcdd. The last a is at position 3, the last b at 4, and the last c at 5. The first block starts at position 0. At position 2, the letter c has last position 5, so reach becomes 5. The scan keeps going until position 5. At that point reach is still 5, so it cuts. The first piece is positions 0 to 5, which has length 6.

The rest of the string is dd, at positions 6 and 7. The letter d last appears at position 7, so reach becomes 7 at position 6. At position 7, reach equals 7, so the scan cuts. The second piece has length 2.

The answer is [6, 2]. Here the cut came exactly when the first block closed. The next block did not need to look back at the first one, since no letter from the first block appears again.

Why cutting early is safe

The method cuts as soon as i equals reach. A reader might ask why it is always safe to cut at that point, and why cutting at that point gives the most pieces.

Let g be the greedy cut, the first position where the scan cuts. Every letter in positions 0 to g has its last occurrence inside that range, so no letter from the first piece appears later. The cut at g is therefore valid.

Now take any valid partition whose first cut is at some position p greater than g. Add one more cut at g. The pieces are then positions 0 to g, positions g + 1 to p, and the rest. The first two pieces do not share a letter. Positions 0 to g are closed, so none of their letters appear after g. The letters in g + 1 to p do not appear after p, because the original partition ended its first piece at p. The partition with the extra cut is valid and has one more piece. So a partition whose first cut is later than g can never have the most pieces, and the best answer always starts with the cut at g.

The same reasoning applies to the rest of the string, which is a smaller version of the same problem. The scan continues from g + 1, and the proof repeats. This is an exchange argument: you show that the greedy choice can always replace any other choice without making the answer worse.

Checking a partition by hand

After you get an answer, you can check it without a program. Cut the string using the sizes in the answer, and write each piece on its own line. Then look at each letter and confirm that it sits in only one piece.

For ababcbacadefegdehijhklij with sizes [9, 7, 8], the pieces are ababcbaca, defegde and hijhklij. The letters a, b and c are in the first piece only. The letters d, e, f and g are in the second piece only. The letters h, i, j, k and l are in the third piece only. A check like this takes a minute and catches a common error, a cut that lands one position too early or too late.

Complexity

The first pass reads the string once. The second pass reads it once more. Each step does a constant amount of work: a lookup in the array, a max, and a comparison. The total time is proportional to the length n of the string, which is written O(n). The space is one array of 26 numbers and the output list. The output list can have as many numbers as the string has letters, so the space used by the output is also at most n.

Common mistakes

Using the first occurrence instead of the last. The method needs the last position of each letter, because the piece must reach that position. If you record the first position, a cut can land between two occurrences of the same letter. For abac, a cut after the first a gives the pieces a and bac, and the letter a is split across both. Check your table by looking at the last index written for each letter.

Overwriting reach instead of taking the maximum. The value of reach must only grow inside a piece. A line like reach = last[s[i] - 'a']; throws away the larger value that an earlier letter set. The scan can then cut in the middle of a block. Always write reach = std::max(reach, ...).

Off-by-one piece lengths. A piece from index start to index i has length i - start + 1. Writing i - start gives a length one too small. For the string a, the length must be 1, not 0. Test with a one-letter string as well as a long one.

Comparing a signed count with an unsigned size. The loop variable i is an int, while s.size() returns a std::size_t. Comparing them directly gives a warning. Here is a small program that does this, compiled with the standard flags.

#include <iostream>
#include <string>
 
int main() {
    std::string s = "abac";
    for (int i = 0; i < s.size(); ++i) {
        std::cout << s[i];
    }
    std::cout << '\n';
}

g++ -std=c++20 -Wall -o signed_compare signed_compare.cpp

The compiler reports this:

signed_compare.cpp: In function 'int main()':
signed_compare.cpp:6:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 |     for (int i = 0; i < s.size(); ++i) {
      |                     ~~^~~~~~~~~~

The fix used in the lesson is const int n = static_cast<int>(s.size());, which converts the size once, before the loop.

Forgetting to subtract the letter a. The index of the letter a is 0, but its character code is 97. Writing last[s[i]] instead of last[s[i] - 'a'] reads far outside the array. Using .at() makes the mistake visible, and the program stops with this message.

terminate called after throwing an instance of 'std::out_of_range'
  what():  array::at: __n (which is 97) >= _Nm (which is 26)

Here __n is the index that was used, and _Nm is the size of the array. Without .at(), the same bad read may silently return garbage, which is harder to find.

Practice

Work each exercise by hand first. Then check your answer by running the function.

1. Find the answer for xyxzy. Write the last position of each letter, then list the cuts.

Show the answer

The last x is at 2, the last y is at 4, and the last z is at 3. At i = 0 the reach is 2. At i = 1 the reach becomes 4 and stays 4 through the end. The scan first reaches 4 at i = 4, so there is one cut. The answer is [5].

2. Find the answer for aabbcc.

Show the answer

The last a is at 1, the last b is at 3, and the last c is at 5. Each letter forms a block of exactly two positions, and each block closes when the scan reaches its last position. The cuts come at positions 1, 3 and 5. The answer is [2, 2, 2].

3. Find the answer for abcde. Explain why the answer has the most pieces possible.

Show the answer

Every letter appears once, so each letter's last position is its own position. At each position i, reach equals i, so the scan cuts after every letter. The answer is [1, 1, 1, 1, 1]. Five pieces is the most any string of five letters can have, because each piece must hold at least one letter.

4. Find the answer for hello.

Show the answer

The last h is at 0, the last e is at 1, the last l is at 3, and the last o is at 4. The cut after h is at position 0 and after e at position 1. The l at positions 2 and 3 forms a block that closes at 3, so its length is 2. The final o is a block of length 1. The answer is [1, 1, 2, 1].

5. Change the function so it returns only the number of pieces, without building the list. Use one integer counter.

Show the answer

Keep the same two passes, but replace the sizes vector with an integer count that starts at 0. Add 1 to count at each cut, and return count at the end. The start variable is no longer needed, because only the number of cuts matters.

int countPartitions(std::string_view s) {
    const int n = static_cast<int>(s.size());
    std::array<int, 26> last{};
    last.fill(-1);
    for (int i = 0; i < n; ++i) {
        last[s[i] - 'a'] = i;
    }
    int count = 0;
    int reach = 0;
    for (int i = 0; i < n; ++i) {
        reach = std::max(reach, last[s[i] - 'a']);
        if (i == reach) {
            ++count;
        }
    }
    return count;
}

For abac this returns 2, which matches the two pieces aba and c.

Summary

• A greedy method makes the best choice it can see at each step and does not revisit it.
• Record the last position of each letter in a first pass over the string.
• Keep a value reach that is the largest last position seen in the current piece, and cut when the scan index equals reach.
• The piece length is i - start + 1, and the next piece starts at i + 1.
• The cut at the earliest possible point gives the most pieces, which an exchange argument proves.
• The method runs in time proportional to the string length, and a common mistake is recording the first occurrence instead of the last.