字符串分割

s = input()
dic = {}
# 找到每个字符的左右区间存在dic中
for i in range(len(s)):
    if s[i] not in dic:
        dic[s[i]] = [i,i]
    else:
        dic[s[i]][1] = i
# 对区间进行排序并合并区间
sort_dic = sorted(dic.items(), key=lambda x:x[1])
stack = [sort_dic[0][1]]
res = []
for key, value in sort_dic[1:]:
    if value[0] < stack[-1][1]:
        stack[-1][1] = max(stack[-1][1], value[1])
    else:
        stack.append(value)
for i, j in stack:
    res.append(str(j-i+1))
print(' '.join(res))

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s = bf.readLine();
        StringBuilder sb = new StringBuilder();
        while (s.length() > 0) {
            int index = s.lastIndexOf(s.charAt(0));//首先找到第一个字符的最后索引的位置，在再这个范围内找出子串的最大长度
            for (int i = 1; i < index; i++) {
                index = Math.max(s.lastIndexOf(s.charAt(i)), index);
            }
            sb.append(index + 1).append(" ");
            s = s.substring(index + 1);
        }
        System.out.println(sb.substring(0, sb.length() - 1).toString());
    }

}

#include <bits/stdc++.h>
using namespace std;

struct P{
    int l,r;
    bool flag;
};

int main(){
    string s;
    cin>>s;
    map<char, P> M;
    int n = s.length();
    for(int i=0;i<n;i++){
        if(M.find(s[i]) == M.end()){
            M[s[i]].l = i;
            M[s[i]].flag = false;
        }
        M[s[i]].r = i;
    }
    if(n==0)
        cout<<0<<endl;
    else{
        int l = M[s[0]].l;
        int r = M[s[0]].r;
        M[s[0]].flag = true;
        for(int i=1;i<n;i++){
            if(M[s[i]].flag)
                continue;
            M[s[i]].flag = true;
            int pl = M[s[i]].l;
            int pr = M[s[i]].r;
            if(pl > r){
                cout<<r-l+1<<" ";
                l = pl;
                r = pr;
            }else if(pr > r)
                r = pr;
        }
        cout<<r-l+1<<endl;
    }
    return 0;
}

""""
找到字母的左右边界，合并有交集的区间
"""

if __name__ == "__main__":
    s = input().strip()
    a = [[-1] * 2 for _ in range(26)]
    for i in range(len(s)):
        if a[ord(s[i]) - ord('a')][0] == -1:
            a[ord(s[i]) - ord('a')][0] = i
        a[ord(s[i]) - ord('a')][1] = i
    a.sort(key=(lambda x: x[0]))
    t, p_max, p_min = 0, 0, 0
    ans = []
    for t in range(0, 26):
        if a[t][0] == -1: continue
        if a[t][0] > p_max:
            ans.append(p_max - p_min + 1)
            p_min = a[t][0]
        p_max = max(p_max, a[t][1])
    ans.append(p_max - p_min + 1)
    print(' '.join(map(str, ans)))

	

m = []
for i in input():
    for j in range(len(m)):
        if i in m[j]:
            m = m[:j] + [''.join(m[j:]) + i]
            break
    else:
        m.append(i)
print(' '.join([str(len(i)) for i in m]))

#include <bits/stdc++.h>

using namespace std;

int main() {
    string ss;
    cin >> ss;
    vector <int> end(26, -1);
    vector <int> ret;
    for (int i = 0; i < (int)ss.length(); i++){
        end[ss[i] - 'a'] = i;
    }
    int d;
    int i = 0;
    int cur = 0;
    while (true){
        cur = 0;
        d = end[ss[i] - 'a'];
        i++;
        while(i <= d){
            d = max(d, end[ss[i] - 'a']);
            i++;
            cur++;
        }
        ret.push_back(cur + 1);
        if(d == (int)ss.length() - 1){
            break;
        }
    }
    for (int i = 0; i < (int)ret.size(); i++){
        if(i){
            cout << " ";
        }
        cout << ret[i];
    }
    cout << endl;
    return 0;
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 *
 *
 * @author jason
 */
public class Main {

	
	/**
	 * 字符串分割
	 *
	 * @param args args
	 */
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String str = scanner.nextLine();
		StringBuilder sb = new StringBuilder();
		while (!"".equals(str)) {
			char[] arr = str.toCharArray();
			int end = 0;
			char next;
			int mid = 0;
			for (int i = 0; i < arr.length; i++) {
				if (i == 0) {
					char s = arr[0];;
					end = str.lastIndexOf(s);
					if (0 == end) {
						sb.append(1).append(" ");
						str = str.substring(1);
						break;
					}
				}
				next = arr[i];
				mid = str.lastIndexOf(next);
				if (mid > end) {
					end = mid;
				}
				if (i == end) {
					int length = mid + 1;
					sb.append(length).append(" ");
					str = str.substring(end + 1);
					break;
				}
			}


		}
		if ("".equals(str)) {
			String trim = sb.toString().trim();
			System.out.println(trim);
		}
	}
}

s = input()
l = len(s)
j = 0
for i in range(l):
    if len(set(list(s[j:i])) & set(list(s[i:l]))) == 0:
        if i > j:        
            print(i-j,end=' ')
            j = i
print(l-j)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(const int argc, const char* argv[]) {
  char input[1024] = "";
  gets(input);
  
  int last_index[26]; // 每个字符最后出现的位置
  int i, len = strlen(input);
  for (i = 0; i < len; ++i)
    last_index[input[i] - 97] = i;
    
  int start = 0, end = 0;
  for (i = 0; i < len; ++i) {
    end = fmax(end, last_index[input[i] - 97]);
    if (i == end) {
      fprintf(stdout, "%d", end - start + 1);
      if (i < len - 1) fputc(32, stdout);
      start = end + 1;
    }
  }
  return 0;
}

//区间合并解法
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <limits.h>
#include <map>

using namespace std;

void stringSplit2() {
    string s;
    cin >> s;
    int len = s.size();
    int start = 0, end = 0;
    //保存字符和该字符在源字符串中出现的最后位置索引
    map<char, int> mp;
    //记录每个字符在字符串中出现的最后位置
    for (int i = 0; i < len; i++) {
        if (mp.find(s[i]) != mp.end()) {
            mp[s[i]] = max(mp[s[i]], i);
        }
        else {
            mp.insert(pair<char, int>(s[i], i));
        }
    }
    //for (auto t: mp) {
    //    cout << t.first << ": " << t.second << endl;
    //}

    //分割字符串
    vector<int> res;
    start = 0, end = mp[s[0]];
    for (int i = 0; i < len; i++) {
        if (i > end) {
            res.push_back(end - start +1);
            start = i;
            end = mp[s[i]];
        }
        else
        {
            end = max(end, mp[s[i]]);
        }
    }
    //最后一段字符串记得存入数组
    res.push_back(end - start + 1);
    //输出
    for (int i = 0; i < res.size(); i++) {
        if (i == res.size() - 1) {
            cout << res[i] << endl;
        }
        else {
            cout << res[i] << " ";
        }
    }
}

int main(){
    stringSplit2();
    return 0;
}

import sys
s = sys.stdin.readline().strip()
N = len(s)
d = dict()
for i in range(N):
    d[s[i]] = i 
start = 0
end = d[s[0]]
i = 1
while i < N:
    if i > end:
        print(i-start, end=' ')
        start = i 
        end = d[s[i]]
        i += 1
    else:
        end = max(end, d[s[i]])
        i += 1
print(i-start)

        List<String> result = new ArrayList<>();
        while (true) {
            if (s.equals("")) {
                break;
            }
            int index = s.lastIndexOf(s.charAt(0));
            String temp = s.substring(0, index + 1);
            for (int i = 0; i < temp.length(); i++) {
                String t = s.substring(i, i + 1);
                int j = s.lastIndexOf(t);
                if (j > index) {
                    index = j;
                }
            }
            result.add(s.substring(0, index + 1));
            s = s.substring(index + 1);
        }


        result.forEach(System.out::println);

#include <cstring>
(803)#include <cstdio>
#include <algorithm>
(831)#include <ctype.h>
#include <iostream>
(720)#include <sstream>
#include <string>
(765)#include <vector>
#include <cmath>
(808)#include <map>
#include <set>
(855)#include <stack>
#include <queue>
//(789)#include <bits/stdc++.h>


using namespace std;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int maxn = 10000 + 100;

#define NUM_ALPHA 26
map<char, int> ch2end;
set<char> alpha;
char ch[maxn];
int is_split[maxn];
int len[NUM_ALPHA + 10];
int ch_len;
int ans;



int main()
{
(2265)#ifdef LOCAL
	freopen("C:\\Users\\lenovo\\Desktop\\test\\in.txt", "r", stdin);
	//freopen("C:\\Users\\lenovo\\Desktop\\test\\out.txt", "w", stdout);
#endif
	while (scanf("%s", ch) == 1)
	{
		ch_len = strlen(ch);
		ch2end.clear();
		for (int i = 0; i < ch_len; i++)
		{
			//if (!ch2end.count(ch[i]))
			//记录右边界
			ch2end[ch[i]] = i;
			
		}

		int k = 0; //当前考虑字符
		int cur_split = 1;
		int start = 0; //区间开始位置
		int end = ch2end[ch[0]]; //区间结束位置
		vector<int> ans;
		while (true)
		{
			if (k > end)
			{
				//记录当前区间，并寻找下一个区间
				ans.push_back(k-start);
				start = k;
				end = ch2end[ch[k]];
				if (k < ch_len)
					continue;
				else
					break;
			}
			
			if (ch2end[ch[k]] > end) end = ch2end[ch[k]];
			k++;

		}

		for (int i = 0; i < ans.size()-1; i++)
			printf("%d ", ans[i]);
		printf("%d\n",ans[ans.size()-1]);
	}


	return 0;
}

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;
int main(void){
    string s;
    int len, index;
    vector<pair<int, int>> v(26, {-1, -1});
    stack<pair<int, int>> stk;    
    cin>>s;
    len = s.length();
    for(int i = 0; i < len; ++i){
        index = s[i] - 'a';
        if(v[index].second == -1){
            v[index].first = i;
            v[index].second = i;
        }
        else
            v[index].first = i;
    }
    sort(v.rbegin(), v.rend());
    len = v.size();
    for(int i = 0; i < len; ++i){
        if(v[i].first == -1)
            continue;
        else if(stk.empty())
            stk.push(v[i]);
        else if(v[i].first < stk.top().second)
            stk.push(v[i]);
        else
            stk.top().second = min(stk.top().second, v[i].second);
    }
    while(true){
        cout<<stk.top().first - stk.top().second + 1;
        stk.pop();
        if(stk.empty()){
            cout<<endl;
            break;
        }else
            cout<<' ';
    }
    return 0;
}

// 思路是用两个map一个map记录str中字符的最左的位置，一个map记录最右的位置
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
int main(){


    string str;
    cin >> str;
    unordered_map<char, int> left, right;
    for(int i = 0; i < str.size(); ++i){
        if(left.find(str[i]) == left.end()){
            left[str[i]] = i;
        }
    }
    for(int i = str.size() - 1; i >= 0; --i){
        if(right.find(str[i]) == right.end()){
            right[str[i]] = i;
        }
    }
    vector<int> res ;
    int l = str.size() - 1, r = 0;
    for(int i = 0; i < str.size(); ++i){
        if(left[str[i]] < l){
            l = left[str[i]];
        }
        if(right[str[i]] > r){
            r = right[str[i]];
        }
        if(i >= r){
            res.push_back(r - l + 1);
            l = str.size() - 1, r = 0;
        }
    }
    for(int i = 0; i < res.size() - 1; ++i){
        cout << res[i] << " ";
    }
    cout << res.back() << endl;
    return 0;
}

s = input()
from collections import defaultdict
d = defaultdict(list)
for i in range(len(s)):
    d[s[i]].append(i)
intervals = []
for i in d:
    intervals.append([min(d[i]), max(d[i])])
intervals = sorted(intervals, key=lambda x:x[0])
res = [intervals[0]]
for i in range(1,len(intervals)):
    if res[-1][1]>intervals[i][0]:
        res[-1][1] = max(res[-1][1], intervals[i][1])
    else:
        res.append(intervals[i])
for i in range(len(res)-1):
    print(res[i][1]-res[i][0]+1, end=' ')
print(res[-1][1]-res[-1][0]+1)