题解

题面描述

给定一个字符串 $s$，要求将其划分为尽可能多的片段，并保证每个片段中同一字母最多出现一次。也就是说，任何一个字母在所有片段中只出现在其中一个片段内。划分后将各个片段按顺序拼接仍然得到原字符串 $s$。

思路

1. 记录每个字母的最后出现位置
   遍历字符串 $s$，用一个数组或字典记录每个字符最后出现的位置。例如，对于字符 $a$，记录其最后一次出现的下标。

2. 划分片段
   从字符串的开头开始遍历，设定当前片段的起始下标为 $start$，终止下标为 $end$。初始时将 $end$ 设为当前字符最后出现的位置。随后继续遍历，更新 $end$ 为遇到的每个字符最后出现位置的最大值。当当前下标 $i$ 等于 $end$ 时，说明从 $start$ 到 $end$ 内所有字符的最后出现位置都包含在这个区间内，此时可以将该区间作为一个合法的片段，然后更新 $start$ 为 $i+1$。

3. 输出结果
   将每个片段的长度输出即可。

代码分析

• 时间复杂度：
  遍历字符串一次获取每个字符最后出现位置，之后再遍历一次进行划分，总体时间复杂度为 $O(n)$，其中 $n$ 为字符串长度。

• 空间复杂度：
  使用了常数级别的额外空间来记录每个字母的最后出现位置，因此空间复杂度为 $O(1)$（因为字母数固定为 $26$）。

C++

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

class Solution {
public:
    // 功能函数：返回每个片段的长度列表
    vector<int> partitionLabels(string s) {
        // 记录每个字母最后出现的位置
        vector<int> last(26, 0);
        for (int i = 0; i < s.size(); i++) {
            last[s[i] - 'a'] = i;
        }
        
        vector<int> res;
        int start = 0, end = 0;
        // 遍历字符串，更新当前区间的最远边界
        for (int i = 0; i < s.size(); i++) {
            end = max(end, last[s[i] - 'a']);
            // 如果当前下标等于区间终止下标，划分一个片段
            if (i == end) {
                res.push_back(end - start + 1);
                start = i + 1;
            }
        }
        return res;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string s;
    cin >> s;  // 输入字符串
    Solution solution;
    vector<int> result = solution.partitionLabels(s);
    
    // 输出每个片段的长度
    for (int len : result) {
        cout << len << " ";
    }
    cout << "\n";
    return 0;
}

Python

# 定义 Solution 类
class Solution:
    def partitionLabels(self, s: str) -> list:
        # 记录每个字母最后出现的位置
        last = {c: i for i, c in enumerate(s)}
        res = []
        start, end = 0, 0
        
        # 遍历字符串，更新当前区间的最远边界
        for i, c in enumerate(s):
            end = max(end, last[c])
            # 如果当前下标等于区间终止下标，则划分一个片段
            if i == end:
                res.append(end - start + 1)
                start = i + 1
        return res

if __name__ == "__main__":
    import sys
    s = sys.stdin.read().strip()
    if s:
        sol = Solution()
        result = sol.partitionLabels(s)
        # 输出每个片段的长度，空格分隔
        print(" ".join(map(str, result)))

Java

import java.util.*;
import java.io.*;

public class Main {
    // 定义 Solution 类
    static class Solution {
        public List<Integer> partitionLabels(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(end - start + 1);
                    start = i + 1;
                }
            }
            return res;
        }
    }
    
    public static void main(String[] args) throws IOException {
        // 使用 BufferedReader 实现输入输出
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        Solution sol = new Solution();
        List<Integer> result = sol.partitionLabels(s);
        // 输出每个片段的长度，空格分隔
        StringBuilder sb = new StringBuilder();
        for (int len : result) {
            sb.append(len).append(" ");
        }
        System.out.println(sb.toString().trim());
    }
}

Leetcode 80.划分字母区间-原题链接

题目内容

给你一个字符串 $s$ 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "$ababcc$" 能够被分为 $["abab", "cc"]$，但类似 $["aba", "bcc"]$ 或 $["ab", "ab", "cc"]$ 的划分是非法的。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 $s$ 。

返回一个表示每个字符串片段的长度的列表。

输入描述

一个字符串 $s$

输出描述

一个表示每个字符串片段的长度的列表

样例1

输入

ababcbacadefegdehijhklij

输出

9 7 8

说明

划分结果为 "$ababcbaca$"、"$defegde$"、"$hijhklij$" 。

每个字母最多出现在一个片段中。

像 "$ababcbacadefegde$", "$hijhklij$" 这样的划分是错误的，因为划分的片段数较少。

样例2

输入

eccbbbbdec

输出

10

提示：

• $1 <= s.length <= 500$
• $s$仅由小写英文字母组成