题目链接

763. 划分字母区间 - 力扣（LeetCode）

题目描述

给定字符串s，尽可能多的划分子串，且每个字母最多出现在同一个片段中

返回划分出字符串子串的长度数组。

输入输出样例

1
2
3
4
5
6
输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

题目解释

每个子串第一次出现的位置和最后一次出现的位置作为区间，计算把所有区间囊括的不重叠区间的个数。

计算每个字符最后出现的位置，然后从左往右扫描数组，如果扫描到对应的字符。

那么字符串的结尾下标不会小于该字符最后出现的位置。

代码

官方实现

作者：力扣官方题解
链接：https://leetcode.cn/problems/partition-labels/solutions/455703/hua-fen-zi-mu-qu-jian-by-leetcode-solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> partitionLabels(string s) {
        int last[26];
        int length = s.size();
        for (int i = 0; i < length; ++i) {
            last[s[i] - 'a'] = i;
        }

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