🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈
 
🍂个人博客首页： KJ.JK
 
💖系列专栏：华为OD机试真题(C++)

一、题目

🔸题目描述

回文串的定义：正读和反读都一样的字符串。
 
现在已经存在一个不包含回文串的字符串，字符串的字符都是在英语字母的前N个，字符串不包含任何长度大于等于2的回文串；
 
请找出下一个字序的不包含回文串的、字符都是在英语字母的前N个、胀度相同的字符串。
如果不存在，请输出NO。

🔸输入输出

输入
输入包括两行。
第一行有一个整数:N (1<=N<=26) ，表示字符串的每个字符范围都是前N的英语字母。
第二行输入一个字符串(输入长度<=10000) ，输入保证这个字符串是合法的并且没有包含回文串。
 
输出
输出下一个字典序的不包含回文串的、字符都是在英语字母的前N个、且长度相同的字符串;
如果不存在，请输出"NO"。

🔸样例1

输入
3cba输出
NO

二、代码参考

#include <iostream>
#include <string>
#include <vector>using namespace std;//深度优先搜索
string dfs(vector<int>& arr, int level, bool limit, int max, vector<int>& path) {//如果已经搜索到了最后一层，返回结果if (level == arr.size()) {string ans = "";for (int num : path) ans += char(num);return ans;}//获取当前层的最小值int min = limit ? arr[level] : 97;//遍历当前层的所有可能值for (int i = min; i <= max; i++) {//如果是当前层的最后一个字符，且当前值等于最小值，则跳过if (limit && level == arr.size() - 1 && i == min) continue;//如果当前字符和上一层字符相同，则跳过if (level >= 1 && i == path[level - 1]) continue;//如果当前字符和上上层字符相同，则跳过if (level >= 2 && i == path[level - 2]) continue;//将当前值加入路径path.push_back(i);//递归搜索下一层string ans = dfs(arr, level + 1, limit && i == min, max, path);//如果找到了结果，直接返回if (!ans.empty()) return ans;//回溯，将当前值从路径中删除path.pop_back();}//如果没有找到结果，返回空字符串return "";
}int main() {int n;string s;cin >> n >> s;vector<int> arr(s.size());for (int i = 0; i < s.size(); i++) arr[i] = int(s[i]);int max = 97 + n - 1;vector<int> path;string ans = dfs(arr, 0, true, max, path);if (ans.empty()) cout << "NO" << endl;else cout << ans << endl;return 0;
}

作者：KJ.JK

文章对你有所帮助的话，欢迎给个赞或者 star，你的支持是对作者最大的鼓励，不足之处可以在评论区多多指正，交流学习