Test-02 幸运N串 ❀

13 May 2020 in Algorithm

• 题目描述：一个全部由大写字母组成的字符串，允许改变最多2个大写字母（也允许不改变或者只改变1个大写字母），使得字符串中所包含的最长的连续的N串的长度最长。

• 输入描述：

  输入的第一行是一个正整数T（0 < T <= 20），表示有T组测试数据。对于每一个测试数据包含一行大写字符串S（0 < |S| <= 50000，|S|表示字符串长度）。 数据范围： 20%的数据中，字符串长度不超过100；
  70%的数据中，字符串长度不超过1000；
  100%的数据中，字符串长度不超过50000。

• 输出描述：

  对于每一组测试样例，输出一个整数，表示操作后包含的最长的连续N串的长度。

• 输入示例：

  3
  NNTN
  NNNNGGNNNN
  NGNNNNGNNNNNNNNSNNNN

• 输出示例：

  4
  10
  18

解题思路：

1、将字符串中的非N字符视为分隔符号，将字符串看作由相隔的几段N串组成;
2、使用动态规划方法，在遍历字符串的过程，m1初始值为上一段N串字符串个数（上一个包括非N字符），m2初始值为上两段N串字符串个数（包括上两个非N字符）；
3、在遍历第三段N串的过程中，count用于记录第三段N串当前已遍历的N个数，m1用于记录前一个串长度+当前串已遍历N个数，m2用于记录前两个N串长度+当前串已遍历N个数；
4、m2每次达到最大值的时候，是刚碰见第三个非N字符的时候，此时m2为三串子N串（包括两个非N字符）长度之和，即为所求幸运N串长度。

AC代码：

// Lucky String N

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();  //T个字符串
        while (T > 0) {
            String str = in.next();
            int count = 0;  //保存当前N串N的个数之和
            int n1 = 0; 
            int n2 = 0;  //保存前1,2段N串N的个数+当前串已遍历N个数之和
            int res = 0;  //最大N串N个数
            for(int i=0; i<str.length(); i++) {
                if (str.charAt(i) == 'N') {
                    count++;
                    n1++;
                    n2++;
                }
                else {
                    n2 = n1 + 1;  //更新m2初始值为上两段长度（包括两个非N字符）
                    n1 = count + 1;  //更新m1初始值为上一段长度（包括非N字符）
                    count = 0;   //更新count初值记录新N串长度
                }
                // 遍历过程中modify2能达到的最大值即为所求的res
                res = Math.max(res, n2);
            }
            System.out.println(res);
            T--;
        }
    }
}

补充说明：

• 这里是牛客编码链接