题解思路与方法

算法核心

本题等价于经典的 “Partition Labels” 问题。 核心贪心思路：对于每个字符，预先记录其在字符串中最后一次出现的位置；然后从左到右扫描，维护当前分片的区间端点 end。遇到字符 c 时，将 end 更新为 max(end, last[c])。若扫描位置 i 正好等于 end，则可在此处分割一个片段。

实现步骤

1. 预处理：扫描字符串，记录每个字符的最后出现下标 last[c]。

2. 分片扫描：初始化 start = 0, end = 0；遍历索引 i：

   • 更新 end = max(end, last[s[i]])；
   • 若 i == end，则当前片段完成，长度为 i - start + 1，将其加入结果，并令 start = i + 1。

3. 返回结果列表。

复杂度分析

• 时间复杂度：

  • 预处理最后出现位置需 $O(n)$，扫描分片再次 $O(n)$，总体 $O(n)$。

• 空间复杂度：

  • 需额外数组/哈希表记录最后出现位置，最多 $O(1)$（字符集固定为 26 个），结果列表占 $O(k)$，其中 $k \le n$。

代码实现

Python 实现

def partition_balloon(s):
    # 记录每个字符最后出现的位置
    last = {c: i for i, c in enumerate(s)}
    res = []
    start = end = 0
    for i, ch in enumerate(s):
        # 更新当前分片最远端点
        end = max(end, last[ch])
        if i == end:
            # 分片完成，记录长度
            res.append(i - start + 1)
            start = i + 1
    return res

if __name__ == "__main__":
    import sys
    # 读取输入字符串
    s = sys.stdin.readline().strip()
    # 获取分组结果
    res = partition_balloon(s)
    # 按要求格式输出列表
    print(res)

Java 实现

import java.util.*;

public class Solution {
    // 分组函数
    public static List<Integer> partitionBalloon(String s) {
        int n = s.length();
        int[] last = new int[26];
        // 记录每个字符最后出现的位置
        for (int i = 0; i < n; i++) {
            last[s.charAt(i) - 'a'] = i;
        }
        List<Integer> res = new ArrayList<>();
        int start = 0, end = 0;
        for (int i = 0; i < n; i++) {
            end = Math.max(end, last[s.charAt(i) - 'a']);
            if (i == end) {
                res.add(i - start + 1);
                start = i + 1;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 读取输入字符串
        String s = in.nextLine().trim();
        in.close();
        // 获取分组结果
        List<Integer> res = partitionBalloon(s);
        // 按要求格式输出列表
        System.out.print("[");
        for (int i = 0; i < res.size(); i++) {
            System.out.print(res.get(i));
            if (i != res.size() - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }
}

C++ 实现

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 分组函数
vector<int> partitionBalloon(const string &s) {
    int n = s.size();
    vector<int> last(26, 0);
    // 记录每个字符最后出现的位置
    for (int i = 0; i < n; ++i) {
        last[s[i] - 'a'] = i;
    }
    vector<int> res;
    int start = 0, end = 0;
    for (int i = 0; i < n; ++i) {
        end = max(end, last[s[i] - 'a']);
        if (i == end) {
            res.push_back(i - start + 1);
            start = i + 1;
        }
    }
    return res;
}

int main() {
    string s;
    // 读取输入字符串
    if (!getline(cin, s)) return 0;
    vector<int> res = partitionBalloon(s);
    // 按要求格式输出列表
    cout << "[";
    for (int i = 0; i < res.size(); ++i) {
        cout << res[i];
        if (i != res.size() - 1) {
            cout << ", ";
        }
    }
    cout << "]";
    return 0;
}

题目内容

公司运动协会正在举办打气球游戏。打气球游戏规则如下：

墙上有一串各种颜色的气球，我们要给他尽可能多的分组，让相同颜色的气球在同一组内。

而且划分完的气球片段按顺序连接起来仍然是原始气球串

请返回一个列表表示划分完的气球片段长度，请注意，如果划分的片段有多个，各个片段之间以逗号和空格分割。

输入描述

一个字符串 $s$ ，代表一串不同颜色的气球。字符串仅仅由小写英文字母组成，$1<=s.length<=500$

输出描述

一个列表，代表划分完之后的每个气球片段的长度。

样例1

输入

abcdeabl

输出

[7, 1]

说明

可以划分为"$abcdeab$"和"$l$"，能保证同一颜色的气球在一个片级中,目获得的片段数量多。两个片段以逗号和空格分割。

样例2

输入

qwerwererrasdfghqccv

输出

[17, 2, 1]

说明

划分结果为"$qwerwererasdfghq$"、"$cc$"、"$v$"。每个颜色的气球只能出现在一个片段中。

像“$qwerwererasdfghgcc$”,"$v$" 这样的划分是错误的，因为划分的片段数不是最多的。三个片段以逗号和空格分割。

样例3

输入

eccbbbbdec

输出

[10]