没有回文串
标题：没有回文串 | 时间限制：1秒 | 内存限制：65536K | 语言限制：不限
回文串的定义：正读和反读都一样的字符串
现在已经存在一个不包含回文串的字符串，字符串的字符都是在英语字母的前N个,且字符串不包含任何长度大于等于2的回文串；请找出下一个字典序的不包含回文串的、字符都是在英语字母的前N个、且长度相同的字符串。如果不存在，请输出NO。
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args)throws IOException{
new Main().start();
}
public void start()throws IOException{
BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
String s =br.readLine();
while(s!=null){
int maxCharNum = Integer.parseInt(s);
String startStr = br.readLine().toLowerCase();
char maxChar = (char)('a'+maxCharNum-1);
String maxStr = getMaxStr(maxCharNum,startStr.length());
String str = addOne(startStr,maxChar);
boolean has = false;
while(compare(maxStr,str)){
if(!checkHuiWenTotal(str)){
System.out.println(str);
has =true;
break;
}
str=addOne(str,maxChar);
}
if(!has){
System.out.println("NO");
}
s=br.readLine();
}
}
public String addOne(String s,char maxChar){
boolean upOne = true;
StringBuilder sb = new StringBuilder(s.length());
for(int i=s.length()-1;i>=0;i--){
char c = s.charAt(i);
if(upOne){
upOne=false;
c = (char)(c+1);
if(c>maxChar){
c='a';
upOne=true;
}
}
sb.append(c);
}
if(upOne){
sb.append('a');
}
return sb.reverse().substring(0);
}
public boolean checkHuiWenTotal(String s){
int maxLength = s.length();
int minLength =2;
int nowLength = maxLength;
while (nowLength>=minLength){
for(int i=0;i<=s.length()-nowLength;i++){
if(checkHuiWen(s.substring(i,i+nowLength))){
return true;
}
}
nowLength--;
}
return false;
}
public boolean checkHuiWen(String s){
int i = 0;
int j = s.length()-1;
char[] charArray = s.toCharArray();
while(i<=j){
if(charArray[i++]!=charArray[j--]){
return false;
}
}
return true;
}
public String getMaxStr(int maxCharNum,int length){
char maxChar = (char)('a'+maxCharNum-1);
StringBuilder sb =new StringBuilder(length);
for(int i=0;i<length;i++){
sb.append(maxChar);
}
return sb.substring(0);
}
public boolean compare(String s1,String s2){
if(s1.length()>s2.length()){
return true;
}
if(s1.length()<s2.length()){
return false;
}
for(int i=0;i<s1.length();i++){
if(s1.charAt(i)>s2.charAt(i)){
return true;
}
if(s1.charAt(i)<s2.charAt(i)){
return false;
}
}
return false;
}
}
