Two Pointer Partition String to Most Unique SubStrings

Given a lowercase alphabet string s, partition s into as many pieces as possible such that each letter appears in at most one piece and return the sizes of the partitions as a list.

Constraints
n ≤ 100,000 where n is the length of s
Example 1
Input
s = “cocoplaydae”
Output
[4, 1, 1, 4, 1]
Explanation
The string is split to[“coco”, “p”, “l”, “ayda”, “e”].

Two Pointer Unique Substring Partition String Algorithm

We need a fixed-size array to index the rightmost position of a letter in the string. Then, we keep moving to the right and update current rightmost window margin.

When we reach the current window margin, we can push the partition location. This greedy approach allows us to partition the string as many substrings as possible where each letter only appears in one substring.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

vector<int> partitionString(string s) {
    int right[26] = {};
    for (int i = 0; i < s.size(); ++ i) {
        right[s[i] - 97] = i;
    }
    vector<int> res;
    int i = 0;
    while (i < s.size()) {
        int curMax = right[s[i] - 97];
        int j = i;
        while (j < curMax) {
            j ++;
            curMax = max(curMax, right[s[j] - 97]);
        }
        res.push_back(curMax - i + 1);
        i = curMax + 1;
    }
    return res;
}

vector<int> partitionString(string s) {
    int right[26] = {};
    for (int i = 0; i < s.size(); ++ i) {
        right[s[i] - 97] = i;
    }
    vector<int> res;
    int i = 0;
    while (i < s.size()) {
        int curMax = right[s[i] - 97];
        int j = i;
        while (j < curMax) {
            j ++;
            curMax = max(curMax, right[s[j] - 97]);
        }
        res.push_back(curMax - i + 1);
        i = curMax + 1;
    }
    return res;
}

The complexity is O(N) as we are traversing the string once.

–EOF (The Ultimate Computing & Technology Blog) —