避重口令小红书 9月13号 笔试真题 第一题题目描述短视频审核后台要把已过审成片的标题按发布时间依次拼接得到小写字符串SSS。SSS的每一个子序列含SSS本身与空串都被视为已经占用的口令不能再给新专题使用。求最短的、不是SSS子序列的小写口令长度。子序列从原串中删除任意个可以为零个字符后剩余字符保持相对顺序所形成的串。输入描述一行仅含小写字母的字符串SSS1≤∣S∣≤1051\le |S|\le 10^51≤∣S∣≤105。输出描述一行一个正整数即最短未占用口令的长度。样例1输入zyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcba输出3说明SSS由两段倒序的262626个小写字母拼接而成。任意单个字母、任意长度为222的小写串都是SSS的子序列前半段取第一个字符、后半段取第二个字符即可。SSS中字母aaa只出现两次故aaa不是子序列最短长度为333。题解和思路思路实现思路动态规划定义dp数组其中dp[i]表示从 S[i...n-1] 开始最短的、不是 S[i...n-1] 子序列的字符串长度对于当前位置i如果某个字符c在s[i...]根本不存在那么单个字符c就已经不是子序列所以dp[i] 1否则选择一个字符c第一次匹配到它的位置是j那么后面还需要找一个不是S[j1...]子序列的字符串。因此dp[i] min(d[i], 1 dp[j] 1)时间复杂度为ONC#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);string s;cins;intns.size();// i之后最近c的位置vectorvectorintnxt(n1,vectorint(26));for(intc0;c26;c){nxt[n][c]n;}for(intin-1;i0;i--){nxt[i]nxt[i1];nxt[i][s[i]-a]i;}constintINF1e9;// 从 S[i...n-1] 开始最短的、不是 S[i...n-1] 子序列的字符串长度vectorintdp(n1,INF);// 空串之后不存在任何字符可以匹配dp[n]1;for(intin-1;i0;i--){for(intc0;c26;c){intjnxt[i][c];if(jn){//字符 c 在后面不存在dp[i]1;}else{dp[i]min(dp[i],1dp[j1]);}}}coutdp[0]endl;return0;}Javaimportjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);Stringssc.next();intns.length();// i之后最近c的位置int[][]nxtnewint[n1][26];for(intc0;c26;c){nxt[n][c]n;}for(intin-1;i0;i--){System.arraycopy(nxt[i1],0,nxt[i],0,26);nxt[i][s.charAt(i)-a]i;}finalintINF1000000000;// 从 S[i...n-1] 开始最短的、不是 S[i...n-1] 子序列的字符串长度int[]dpnewint[n1];Arrays.fill(dp,INF);// 空串之后不存在任何字符可以匹配dp[n]1;for(intin-1;i0;i--){for(intc0;c26;c){intjnxt[i][c];if(jn){// 字符 c 在后面不存在dp[i]1;}else{dp[i]Math.min(dp[i],1dp[j1]);}}}System.out.println(dp[0]);}}pythonimportsys ssys.stdin.readline().strip()nlen(s)# i之后最近c的位置nxt[[n]*26for_inrange(n1)]foriinrange(n-1,-1,-1):nxt[i]nxt[i1].copy()nxt[i][ord(s[i])-ord(a)]i INF10**9# 从 S[i...n-1] 开始最短的、不是 S[i...n-1] 子序列的字符串长度dp[INF]*(n1)# 空串之后不存在任何字符可以匹配dp[n]1foriinrange(n-1,-1,-1):forcinrange(26):jnxt[i][c]ifjn:# 字符 c 在后面不存在dp[i]1else:dp[i]min(dp[i],1dp[j1])print(dp[0])Javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});rl.on(line,(s){ss.trim();constns.length;// i之后最近c的位置constnxtArray.from({length:n1},()newArray(26).fill(n));for(letc0;c26;c){nxt[n][c]n;}for(letin-1;i0;i--){nxt[i][...nxt[i1]];nxt[i][s.charCodeAt(i)-97]i;}constINF1e9;// 从 S[i...n-1] 开始最短的、不是 S[i...n-1] 子序列的字符串长度constdpnewArray(n1).fill(INF);// 空串之后不存在任何字符可以匹配dp[n]1;for(letin-1;i0;i--){for(letc0;c26;c){constjnxt[i][c];if(jn){// 字符 c 在后面不存在dp[i]1;}else{dp[i]Math.min(dp[i],1dp[j1]);}}}console.log(dp[0]);rl.close();});Gopackagemainimport(bufiofmtos)funcmain(){in:bufio.NewReader(os.Stdin)out:bufio.NewWriter(os.Stdout)deferout.Flush()varsstringfmt.Fscan(in,s)n:len(s)// i之后最近c的位置nxt:make([][]int,n1)fori:0;in;i{nxt[i]make([]int,26)forc:0;c26;c{nxt[i][c]n}}fori:n-1;i0;i--{copy(nxt[i],nxt[i1])nxt[i][s[i]-a]i}constINFint(1e9)// 从 S[i...n-1] 开始最短的、不是 S[i...n-1] 子序列的字符串长度dp:make([]int,n1)fori:0;in;i{dp[i]INF}// 空串之后不存在任何字符可以匹配dp[n]1fori:n-1;i0;i--{forc:0;c26;c{j:nxt[i][c]ifjn{// 字符 c 在后面不存在dp[i]1}else{ifdp[i]1dp[j1]{dp[i]1dp[j1]}}}}fmt.Fprintln(out,dp[0])}