华为OD机试真题 - 没有回文串 (D卷,200分)

题目描述

回文串的定义：正读和反读都一样的字符串。

现在已经存在一个不包含回文串的字符串，字符串的字符都是在英语字母的前N个,且字符串不包含任何长度大于等于2的回文串；

请找出下一个字典序的不包含回文串的、字符都是在英语字母的前N个、且长度相同的字符串。

如果不存在，请输出NO。

目录

题目描述

输入描述

输出描述

用例

题目解析

Java算法源码

JS算法源码

Python算法源码

C算法源码

华为机试有三道题目，第一道和第二道属于简单或中等题，分值为100分，第三道为中等或困难题，分值为200分。总分为400分，150分钟，机试是在牛客考试，练习的时候也可以在牛客网练习，提前熟悉操作

https://ac.nowcoder.com/acm/contest/5652/K

点击上方链接进入牛客练习界面，可以自定义题目，自定义输入、输出等等，华为OD真实机试环境，非其他第三方平台模拟。

输入描述

输入包括两行。

第一行有一个整数:N（1<=N<=26），表示字符串的每个字符范围都是前N的英语字母。

第二行输入一个字符串S（输入长度<=10000），输入保证这个字符串是合法的并且没有包含回文串。

输出描述

输出下一个字典序的不包含回文串的、字符都是在英语字母的前N个、且长度相同的字符串；

如果不存在,请输出”NO“。

用例

题目解析

1. 首先，我们需要找到输入字符串S的下一个字典序的字符串。
2. 然后，我们需要检查这个新字符串是否包含回文串。如果包含，我们需要继续寻找下一个字典序的字符串，直到找到一个不包含回文串的字符串。
3. 如果找不到这样的字符串，输出"NO"。

Java算法源码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        String s = sc.next();

        System.out.println(getResult(n, s));
    }

    public static String getResult(int n, String s) {
        char[] chars = s.toCharArray();
        char limit = (char) ('a' + n - 1);
        boolean back = false;

        for (int i = chars.length - 1; i >= 0; i--) {
            if (chars[i] < limit) {
                if (!back) {
                    chars[i] += 1;
                } else {
                    back = false;
                }

                if (i - 1 >= 0 && chars[i] == chars[i - 1]) continue;
                if (i - 2 >= 0 && chars[i] == chars[i - 2]) continue;

                return new String(chars);
            } else {
                chars[i] = 'a';
                back = true;
            }
        }

        return "NO";
    }
}

JS算法源码

const rl = r