)
没有回文串
2025华为OD机试 - 华为OD上机考试 200分题型
华为OD机试真题目录点击查看: 华为OD机试真题题库目录｜机考题库 + 算法考点详解
题目描述
回文串的定义：正读和反读都一样的字符串。
现在已经存在一个不包含回文串的字符串，字符串的字符都是在英语字母的前N个,且字符串不包含任何长度大于等于2的回文串；
请找出下一个字典序的不包含回文串的、字符都是在英语字母的前N个、且长度相同的字符串。
如果不存在，请输出NO。
输入描述
输入包括两行。
第一行有一个整数:N（1<=N<=26），表示字符串的每个字符范围都是前N的英语字母。
第二行输入一个字符串S（输入长度<=10000），输入保证这个字符串是合法的并且没有包含回文串。
输出描述
输出下一个字典序的不包含回文串的、字符都是在英语字母的前N个、且长度相同的字符串；
如果不存在,请输出”NO“。
用例1
输入
3 cba输出
NO题解
思路:贪心
- 回文串去掉首尾字母后，仍然是回文串，所以长度为
m的回文串必然包含长为m-2的回文串。逆推可以得到如果字符串不包含m-2长度的回文串，就不会存在长为m的回文串。综合题目中描述的字符串不包含任何长度大于等于2的回文串, 可以推导出不包含长度2和长度3的回文串就不会包含回文串。 - 判断是否存在回文串就转换为如何判断
不包含长度2和长度3的回文串,那这个就比较简单了，存在i如果s[i] == s[i+1] || s[i] == s[i+2]那就是存在了。 - 题目要求字典序最小，相应增大位置越靠右越好，这道题可以理解成
s字符串的字符串n进制加数。 - 这题可以采用
贪心 + 类似进位：一开始对最右位执行+1操作，- 如果不与前1位、前2位相等则说明符合要求输出结果。
- 一旦发生冲突则继续加，溢出就进位
- 如果到最左边还出现溢出则说明不存在合法返回NULL。
- 假设当前由于溢出到达
index位置，并且index位置值不和前1前2位发生冲突，则说明index位已经合法代表[0,index]都是合法(不包含回文串)的，接下就是回溯考虑{index+1, s.size()-1}是否合法，这里就是循环遍历这个范围内所有位置是否和前两个值发生冲突，- 全部不发生冲突的话，说明合法，直接输出。
- 假设x位置发生冲突的话，则继续重复上面发生冲突的逻辑处理即可。
c++
#include<iostream> #include<vector> #include<string> #include <utility> #include <sstream> #include<algorithm> #include<cmath> #include<map> using namespace std; string handle(string s, int k) { k += 'a'; int n = s.size(); int i = n - 1; s[i]++; while (i < n) { // 需要进位 if (s[i] == k) { if (i == 0) { return "NO"; } // 进位 s[i] = 'a'; s[--i]++; } else if (i && s[i] == s[i-1] || i > 1 && s[i] == s[i-2]) { // 如果 s[i] 和左侧的字符形成回文串，就继续增加 s[i] s[i]++; } else { i++; } } return s; } int main() { string s; int k; cin >> k; cin >> s; string res = handle(s, k); cout << res; return 0; }JAVA
import java.util.*; public class Main { static String handle(String s, int k) { char[] arr = s.toCharArray(); char limit = (char) ('a' + k); int n = arr.length; int i = n - 1; arr[i]++; // 从最后一位开始尝试递增 while (i < n) { // 需要进位 if (arr[i] == limit) { if (i == 0) { return "NO"; } arr[i] = 'a'; i--; arr[i]++; } // 如果当前字符与前1位或前2位形成回文 else if ((i >= 1 && arr[i] == arr[i - 1]) || (i >= 2 && arr[i] == arr[i - 2])) { arr[i]++; } // 当前位合法，处理下一位 else { i++; } } return new String(arr); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int k = sc.nextInt(); String s = sc.next(); System.out.println(handle(s, k)); } }Python
defhandle(s,k):arr=list(s)limit=chr(ord('a')+k)n=len(arr)i=n-1arr[i]=chr(ord(arr[i])+1)# 最后一位递增whilei<n:# 需要进位ifarr[i]==limit:ifi==0:return"NO"arr[i]='a'i-=1arr[i]=chr(ord(arr[i])+1)# 与前1位或前2位形成回文elif(i>=1andarr[i]==arr[i-1])or\(i>=2andarr[i]==arr[i-2]):arr[i]=chr(ord(arr[i])+1)else:i+=1return''.join(arr)if__name__=="__main__":k=int(input().strip())s=input().strip()print(handle(s,k))JavaScript
'use strict';constreadline=require('readline');constrl=readline.createInterface({input:process.stdin,output:process.stdout});letlines=[];rl.on('line',(line)=>{if(line!==null){lines.push(line.trim());}});rl.on('close',()=>{letidx=0;constk=parseInt(lines[idx++]);// 字母个数consts=lines[idx++];// 原字符串console.log(handle(s,k));});functionhandle(s,k){letarr=s.split('');letlimit=String.fromCharCode('a'.charCodeAt(0)+k);letn=arr.length;// 从最后一位开始尝试递增leti=n-1;arr[i]=String.fromCharCode(arr[i].charCodeAt(0)+1);while(i<n){// 需要进位if(arr[i]===limit){if(i===0){return"NO";}arr[i]='a';i--;arr[i]=String.fromCharCode(arr[i].charCodeAt(0)+1);}// 如果与前1位或前2位形成回文elseif((i>=1&&arr[i]===arr[i-1])||(i>=2&&arr[i]===arr[i-2])){arr[i]=String.fromCharCode(arr[i].charCodeAt(0)+1);}// 当前位合法，继续处理下一位else{i++;}}returnarr.join('');}Go
packagemainimport("bufio""fmt""os")funchandle(sstring,kint)string{arr:=[]byte(s)limit:=byte('a'+k)n:=len(arr)i:=n-1arr[i]++// 从最后一位开始递增fori<n{// 需要进位ifarr[i]==limit{ifi==0{return"NO"}arr[i]='a'i--arr[i]++}elseif(i>=1&&arr[i]==arr[i-1])||(i>=2&&arr[i]==arr[i-2]){// 与前1位或前2位形成回文arr[i]++}else{i++}}returnstring(arr)}funcmain(){in:=bufio.NewReader(os.Stdin)varkintvarsstringfmt.Fscan(in,&k)fmt.Fscan(in,&s)fmt.Println(handle(s,k))})
