当前位置：首页 > news >正文

阿里巴巴算法岗笔试真题【坏掉的键盘】

news 2026/6/28 22:20:54

坏掉的键盘(C++/Py/Java /Js/Go)题解

阿里算法岗 0523笔试第二题

题目内容

小明准备输入一个仅由小写英文字母组成的字符串，但他的键盘在一开始就有且仅有一个按键失灵，导致该字母在原串中的所有出现都没有被输入，最终得到的字符串为sss。小明还告诉你：原本要输入的完整字符串中任意相邻两个字符都不相同。
请你计算，对于每一个可能的小写字母ccc（‘aaa’ 到 ‘zzz’），有多少个满足条件的原始字符串（删除所有ccc后得到sss，且自身相邻字符不同）。请输出将这些情况下得到的数量相加后的总和。由于答案可能很大，结果对109+710^9 + 7109+7取模。

输入描述

每个测试文件包含多组测试数据。第一行输入一个整数T (1≤T≤105)T\ (1 \le T \le 10^5)T(1≤T≤105)表示数据组数。接下来每组数据描述如下：

第一行输入一个整数n (1≤n≤2×105)n\ (1 \le n \le 2 \times 10^5)n(1≤n≤2×105)表示字符串的长度。
第二行输入一个仅由小写字母组成的字符串sss。
保证所有测试数据中字符串长度总和不超过5×1055 \times 10^55×105。

输出描述

对于每组测试数据，输出一个整数，表示“可能的原始字符串”的数量对109+710^9 + 7109+7取模后的结果。

样例1

输入

3 4 abac 4 aaaa 3 xyz

输出

736 100 368

题解

思路

逻辑分析

首先坏掉的键盘肯定是s中未出现字符，初始先统计未出现字符种类个数，count。
首尾两个位置确实各自有两种选择（插或不插），对结果产生影响为2 * 2
不考虑内部情况暂时得到的结果为res = count * 2 * 2,接下来考虑s字符相关性
- 相邻字符不同，中间可以插也可以不插（2 种），res * 2
- 若相邻字符相同，中间必须插入失灵字符（只有 1 种）
总体算法时间复杂度为O(n)

C++

#include<bits/stdc++.h>usingnamespacestd;constlongMOD=1e9+7;intmain(){ios_base::sync_with_stdio(false);cin.tie(nullptr);intT;cin>>T;while(T--){intn;cin>>n;string s;cin>>s;vector<int>flag(26,false);// 统计未出现字符数量intcount=26;for(inti=0;i<n;i++){charc=s[i];if(!flag[c-'a']){flag[c-'a']=true;count--;}}longres=count;// 首尾都可额外添加或不添加 2*2res*=4;// 考虑两个字符for(inti=1;i<n;i++){// 不等于情况，中间可插入或不插入失灵字符if(s[i]!=s[i-1]){res=(res*2)%MOD;}}cout<<res<<endl;}return0;}

java

importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;importjava.util.StringTokenizer;publicclassMain{staticfinallongMOD=1000000007L;publicstaticvoidmain(String[]args)throwsIOException{BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));intT=Integer.parseInt(br.readLine());while(T-->0){intn=Integer.parseInt(br.readLine());Strings=br.readLine();boolean[]flag=newboolean[26];// 统计未出现字符数量intcount=26;for(inti=0;i<n;i++){charc=s.charAt(i);if(!flag[c-'a']){flag[c-'a']=true;count--;}}longres=count;// 首尾都可额外添加或不添加 2*2res*=4;// 考虑两个字符for(inti=1;i<n;i++){// 不等于情况，中间可插入或不插入失灵字符if(s.charAt(i)!=s.charAt(i-1)){res=(res*2)%MOD;}}System.out.println(res);}}}

python

MOD=10**9+7T=int(input())for_inrange(T):n=int(input())s=input()flag=[False]*26# 统计未出现字符数量count=26forcins:idx=ord(c)-ord('a')ifnotflag[idx]:flag[idx]=Truecount-=1res=count# 首尾都可额外添加或不添加 2*2res*=4# 考虑两个字符foriinrange(1,n):# 不等于情况，中间可插入或不插入失灵字符ifs[i]!=s[i-1]:res=(res*2)%MODprint(res)

javascript

constreadline=require("readline");constrl=readline.createInterface({input:process.stdin,output:process.stdout});constinput=[];rl.on("line",(line)=>{input.push(line);});rl.on("close",()=>{constMOD=1000000007n;letidx=0;constT=Number(input[idx++]);constans=[];for(lett=0;t<T;t++){constn=Number(input[idx++]);consts=input[idx++];constflag=newArray(26).fill(false);// 统计未出现字符数量letcount=26;for(leti=0;i<n;i++){constc=s.charCodeAt(i)-97;if(!flag[c]){flag[c]=true;count--;}}letres=BigInt(count);// 首尾都可额外添加或不添加 2*2res*=4n;// 考虑两个字符for(leti=1;i<n;i++){// 不等于情况，中间可插入或不插入失灵字符if(s[i]!==s[i-1]){res=(res*2n)%MOD;}}ans.push(res.toString());}console.log(ans.join("\n"));});

Go

packagemainimport("bufio""fmt""os")constMODint64=1000000007funcmain(){in:=bufio.NewReader(os.Stdin)varTintfmt.Fscan(in,&T)out:=bufio.NewWriter(os.Stdout)deferout.Flush()for;T>0;T--{varnintvarsstringfmt.Fscan(in,&n)fmt.Fscan(in,&s)flag:=make([]bool,26)// 统计未出现字符数量count:=26fori:=0;i<n;i++{c:=s[i]-'a'if!flag[c]{flag[c]=truecount--}}varresint64=int64(count)// 首尾都可额外添加或不添加 2*2res*=4// 考虑两个字符fori:=1;i<n;i++{// 不等于情况，中间可插入或不插入失灵字符ifs[i]!=s[i-1]{res=(res*2)%MOD}}fmt.Fprintln(out,res)}}