给定一个由小写字母组成的字符串s,请将其分割成尽量多的子串,并保证每个字母最多只在其中一个子串中出现。请返回由一个或多个整数表示的分割后各子串的长度。
给定一个由小写字母组成的字符串s,请将其分割成尽量多的子串,并保证每个字母最多只在其中一个子串中出现。请返回由一个或多个整数表示的分割后各子串的长度。
来自标准输入的一行由小写字母组成的字符串。
字符串最优分割后各子串的长度,多个数字之间由空格分隔。
ababbacadefgdehijhklij
8 6 8
该样例下最优的分割为"ababbaca" + "defgde" + "hijhklij",在该分割下字母abc仅出现在"ababbaca"中、字母defg仅出现在"defgde"中、字母hijkl仅出现在"hijhklij"中
要求将其“分割为尽量多的子串”意味着像"ababbacadefgde" + "hijhklij"这样的分割也是合法的,但在本题中并不是最优解
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)))
const readline = require('readline') const rl = readline.createInterface({ input: process.stdin, ouput: process.stdout }) let inArr = [] rl.on('line',line=>{ if(!line) return inArr.push(line.trim()) if(inArr.length === 1){ let str = inArr[0].split('') let res = [] let right = 0 for (let i = 0; i < str.length; i++) { let temp = str[i] let index = str.lastIndexOf(temp) if(i<=right){ right = Math.max(right, index) }if(i>right){ res.push(right+1) str= str.slice(right+1) right =0 i=-1 } } res.push(str.length) console.log(res.join(' ')) } })
#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); } } }
#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; }
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; }
string=input().strip() ans=[] pos={} n=len(string) for i in range(n): if not string[i] in pos: pos[string[i]]=i for j in range(n-1,i,-1): if string[j]==string[i]: pos[string[i]]=j break i=0 while i<n: max_k=pos[string[i]] j=i+1 while j<=max_k: max_k=max(max_k,pos[string[j]]) j+=1 ans.append(j-i) i=j print(' '.join(map(str,ans))
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))
#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; }统计并合并字符出现位置的区间,只出现一次的字符区间为[i, i]不和其他区间合并,这里从左到右输出字符串分割的大小,比较的是最后一次出现位置,按降序排序,注意输出格式
// 思路是用两个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)