)
避重口令
小红书 9月13号 笔试真题 第一题
题目描述
短视频审核后台要把已过审成片的标题按发布时间依次拼接，得到小写字符串SSS。SSS的每一个子序列（含SSS本身与空串）都被视为已经占用的口令，不能再给新专题使用。
求最短的、不是SSS子序列的小写口令长度。
子序列：从原串中删除任意个（可以为零个）字符后，剩余字符保持相对顺序所形成的串。
输入描述
一行，仅含小写字母的字符串SSS（1≤∣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[j+1...]子序列的字符串。因此dp[i] = min(d[i], 1 + dp[j] + 1)
- 如果某个字符
- 时间复杂度为
O（N）
C++
#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);string s;cin>>s;intn=s.size();// i之后最近c的位置vector<vector<int>>nxt(n+1,vector<int>(26));for(intc=0;c<26;c++){nxt[n][c]=n;}for(inti=n-1;i>=0;i--){nxt[i]=nxt[i+1];nxt[i][s[i]-'a']=i;}constintINF=1e9;// 从 S[i...n-1] 开始，最短的、不是 S[i...n-1] 子序列的字符串长度vector<int>dp(n+1,INF);// 空串之后，不存在任何字符可以匹配dp[n]=1;for(inti=n-1;i>=0;i--){for(intc=0;c<26;c++){intj=nxt[i][c];if(j==n){//字符 c 在后面不存在dp[i]=1;}else{dp[i]=min(dp[i],1+dp[j+1]);}}}cout<<dp[0]<<endl;return0;}Java
importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);Strings=sc.next();intn=s.length();// i之后最近c的位置int[][]nxt=newint[n+1][26];for(intc=0;c<26;c++){nxt[n][c]=n;}for(inti=n-1;i>=0;i--){System.arraycopy(nxt[i+1],0,nxt[i],0,26);nxt[i][s.charAt(i)-'a']=i;}finalintINF=1000000000;// 从 S[i...n-1] 开始，最短的、不是 S[i...n-1] 子序列的字符串长度int[]dp=newint[n+1];Arrays.fill(dp,INF);// 空串之后，不存在任何字符可以匹配dp[n]=1;for(inti=n-1;i>=0;i--){for(intc=0;c<26;c++){intj=nxt[i][c];if(j==n){// 字符 c 在后面不存在dp[i]=1;}else{dp[i]=Math.min(dp[i],1+dp[j+1]);}}}System.out.println(dp[0]);}}python
importsys s=sys.stdin.readline().strip()n=len(s)# i之后最近c的位置nxt=[[n]*26for_inrange(n+1)]foriinrange(n-1,-1,-1):nxt[i]=nxt[i+1].copy()nxt[i][ord(s[i])-ord('a')]=i INF=10**9# 从 S[i...n-1] 开始，最短的、不是 S[i...n-1] 子序列的字符串长度dp=[INF]*(n+1)# 空串之后，不存在任何字符可以匹配dp[n]=1foriinrange(n-1,-1,-1):forcinrange(26):j=nxt[i][c]ifj==n:# 字符 c 在后面不存在dp[i]=1else:dp[i]=min(dp[i],1+dp[j+1])print(dp[0])Javascript
constreadline=require('readline');constrl=readline.createInterface({input:process.stdin,output:process.stdout});rl.on('line',(s)=>{s=s.trim();constn=s.length;// i之后最近c的位置constnxt=Array.from({length:n+1},()=>newArray(26).fill(n));for(letc=0;c<26;c++){nxt[n][c]=n;}for(leti=n-1;i>=0;i--){nxt[i]=[...nxt[i+1]];nxt[i][s.charCodeAt(i)-97]=i;}constINF=1e9;// 从 S[i...n-1] 开始，最短的、不是 S[i...n-1] 子序列的字符串长度constdp=newArray(n+1).fill(INF);// 空串之后，不存在任何字符可以匹配dp[n]=1;for(leti=n-1;i>=0;i--){for(letc=0;c<26;c++){constj=nxt[i][c];if(j===n){// 字符 c 在后面不存在dp[i]=1;}else{dp[i]=Math.min(dp[i],1+dp[j+1]);}}}console.log(dp[0]);rl.close();});Go
packagemainimport("bufio""fmt""os")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,n+1)fori:=0;i<=n;i++{nxt[i]=make([]int,26)forc:=0;c<26;c++{nxt[i][c]=n}}fori:=n-1;i>=0;i--{copy(nxt[i],nxt[i+1])nxt[i][s[i]-'a']=i}constINF=int(1e9)// 从 S[i...n-1] 开始，最短的、不是 S[i...n-1] 子序列的字符串长度dp:=make([]int,n+1)fori:=0;i<=n;i++{dp[i]=INF}// 空串之后，不存在任何字符可以匹配dp[n]=1fori:=n-1;i>=0;i--{forc:=0;c<26;c++{j:=nxt[i][c]ifj==n{// 字符 c 在后面不存在dp[i]=1}else{ifdp[i]>1+dp[j+1]{dp[i]=1+dp[j+1]}}}}fmt.Fprintln(out,dp[0])}
