描述

Catcher是MCA国的情报员，他工作时发现敌国会用一些对称的密码进行通信，比如像这些ABBA，ABA，A，123321，但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。比如进行下列变化 ABBA->12ABBA,ABA->ABAKK,123321->51233214　。因为截获的串太长了，而且存在多种可能的情况（abaaab可看作是aba,或baaab的加密形式），Cathcer的工作量实在是太大了，他只能向电脑高手求助，你能帮Catcher找出最长的有效密码串吗？

数据范围：字符串长度满足 1≤n≤2500

输入描述：输入一个字符串（字符串的长度不超过2500）

输出描述：返回有效密码串的最大长度

示例1

输入：
ABBA


输出：
4

示例2

输入：
ABBBA

输出：
5

示例3

输入：
12HHHHA


输出：
4

解法

那就是不断尝试遍历来查找最优解。

  • 针对ABA型：可以先取字符串的第二个字符作为中间位置开始尝试（第一个字形成不了对称，所以无需尝试），直到字符串的倒数第二个字符为止。而后从该中间位置往两边不断尝试，如果两边不对称，则从中间位置查找下个位置作为中间位置，再次尝试，直到所有位置尝试完成。
  • 针对ABBA型：可以先取字符串的第1个字符作为中间位置的左半边开始尝试，直到字符串的倒数第二个字符为止。如果找到了右边与左半边相同的字符，则这两个字符组成中间位置，而后从该中间位置往两边不断尝试，如果两边不对称，则从中间位置查找下个位置作为中间位置，再次尝试，直到所有位置尝试完成。
/*
 * Copyright (c) waylau.com, 2022. All rights reserved.
 */

package com.waylau.nowcoder.exam.oj.huawei;

import java.util.Scanner;

/**
 * HJ32 密码截取.
 * 描述：该题目是一道密码加密题，密码混合在复杂字符串中，是一个对称子字符串，
 * 比如12321AABC，则真正要提取的是12321，因为它是对称的，
 * 所以需要写一个程序来实现快速的提取。题目要求提取最长的密码长度。
 * 输入描述：输入一个字符串
 * 输出描述：返回有效密码串的最大长度
 * 示例：
 * 输入：12321AABC
 * 输出：5
 *
 * @author <a href="">Way Lau</a>
 * @since 2022-08-17
 */
public class HJ032PasswordIntercept {
    public static void main(String[] args) {
        // 输入
        Scanner sc = new Scanner(System.in);
        String in = sc.nextLine();

        // 转为字符
        char[] array = in.toCharArray();

        // 不管怎么样，如果没有形成
        int len = 1;
        int maxLen = 1;

        // 先处理ABA型
        for (int i = 1; i < array.length - 2; i++) {
            int leftIndex = i - 1;
            int rightIndex = i + 1;

            // 向左、向右尝试，不要超过边界
            while (leftIndex >= 0 && rightIndex <= array.length - 1) {
                // 左右对称，则尝试下个位置
                if (array[leftIndex] == array[rightIndex]) {
                    len = rightIndex - leftIndex + 1;
                    leftIndex--;
                    rightIndex++;

                    // 记录最大值
                    maxLen = Math.max(maxLen, len);
                } else {
                    break;
                }
            }
        }

        // 再处理ABBA型
        for (int i = 1; i < array.length - 2; i++) {
            int leftIndex = i - 1;
            int rightIndex = i + 2;

            // 向左、向右尝试，不要超过边界
            while (leftIndex >= 0 && rightIndex <= array.length - 1) {
                // 左右对称，则尝试下个位置
                if ((array[i] == array[i+1]) && (array[leftIndex] == array[rightIndex])) {
                    len = rightIndex - leftIndex + 1;
                    leftIndex--;
                    rightIndex++;

                    // 记录最大值
                    maxLen = Math.max(maxLen, len);
                } else {
                    break;
                }
            }
        }


        // 输出
        System.out.println(maxLen);

        // 关闭
        sc.close();
    }
}

参考引用