微软第二题 Composition
一开始时间复杂度为 N*N的做法超时，然后换成C++写了一下还是TLE。
然后换成26*N后AC 了
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int N,M;
static int[][] map;
static int[] numlist;
static String str;
static int res;
static int[] dp;
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int a,b;
while(sc.hasNext()){
N=sc.nextInt();
str=sc.next();
numlist=new int[N];
map=new int[26][26];
dp=new int[26];
for(int i=0;i<N;i++){
numlist[i]=str.charAt(i)-'a';
}
M=sc.nextInt();
for(int i=0;i<M;i++){
str=sc.next();
a=str.charAt(0)-'a';
b=str.charAt(1)-'a';
map[a][b]=1;
map[b][a]=1;
}
for(int i=0;i<N;i++){
if(dp[numlist[i]]>0){
if(map[numlist[i]][numlist[i]]!=1) dp[numlist[i]]=dp[numlist[i]]+1;
}
else dp[numlist[i]]=1;
for(int j=0;j<26;j++){
if(map[numlist[i]][j]!=1&&dp[j]>0&&numlist[i]!=j){
dp[numlist[i]]=Math.max(dp[numlist[i]], dp[j]+1);
}
}
}
res=1;
for(int i=0;i<26;i++){
res=Math.max(res, dp[i]);
}
System.out.println(N-res);
}
}
}
