给定一个由小写字母组成的字符串s,请将其分割成尽量多的子串,并保证每个字母最多只在其中一个子串中出现。请返回由一个或多个整数表示的分割后各子串的长度。
给定一个由小写字母组成的字符串s,请将其分割成尽量多的子串,并保证每个字母最多只在其中一个子串中出现。请返回由一个或多个整数表示的分割后各子串的长度。
来自标准输入的一行由小写字母组成的字符串。
字符串最优分割后各子串的长度,多个数字之间由空格分隔。
ababbacadefgdehijhklij
8 6 8
该样例下最优的分割为"ababbaca" + "defgde" + "hijhklij",在该分割下字母abc仅出现在"ababbaca"中、字母defg仅出现在"defgde"中、字母hijkl仅出现在"hijhklij"中
要求将其“分割为尽量多的子串”意味着像"ababbacadefgde" + "hijhklij"这样的分割也是合法的,但在本题中并不是最优解
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(' ')) } })