划分字母区间

题意

将字符串划分为尽可能多的片段，同一字母只出现在一个片段中。

思路

先预处理每个字母的最后出现位置 last[c]。扫描时维护当前段边界 end：遇到字符 c 时更新 end = max(end, last[c])。当扫描位置 i 到达 end 时，说明当前段内所有字母的末次出现都已包含，可以切分。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int last[26] = {};
        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;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    for (int x : Solution().partitionLabels(s))
        cout << x << ' ';
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24#!/usr/bin/env python3
from typing import List


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


def main():
    s = input().strip()
    print(*Solution().partitionLabels(s))


if __name__ == "__main__":
    main()

复杂度

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

总结

划分字母区间是贪心的典型：每段尽可能短，但必须包含段内所有字母的末次出现。end 的扩展保证了"不遗漏"，到达 end 时切分保证了"不冗余"。

目录

题意

思路

代码

复杂度

总结