题解 | 密码验证合格程序

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            if (str.length() < 8) {
                System.out.println("NG");
                continue;
            }
            int part = 0;  //含几种
            if (str.matches(".*[a-z].*")) part++;  //有小写字符
            if (str.matches(".*[A-Z].*")) part++;  //有大写字符
            if (str.matches(".*[0-9].*")) part++;  //有数字
            if (str.matches(".*[^0-9a-zA-Z].*")) part++;  //有特殊字符
            if (part < 3) {
                System.out.println("NG");
                continue;
            }

            //判断不含子串
            //关键：子串要独立，即不能重叠
            //优化：只要检查有无长度为3的两个独立子串就行，因为要是有长度更长的独立子串，在长度为3时就检查出来了
            boolean contain = false;
            int len = 3;  //只检查长度为3的子串
            for (int i = 0; i + len * 2 <= str.length(); i++) {  //i:子串开头
                String str1 = str.substring(i, i + len);
                String left = str.substring(i + len);
                if (left.contains(str1)) {
                    contain = true;
                    break;
                }
            }

            //(优化前)子串长度小于字符串的一半，保证不和另一串子串重叠
            /*for (int len = 3; len <= str.length() / 2; len++) {
                if (contain) break;
                for (int i = 0; i + len * 2 <= str.length(); i++) {  //i:子串开头
                    String str1 = str.substring(i, i + len);
                    String left = str.substring(i + len);
                    if (left.contains(str1)) {
                        contain = true;
                        break;
                    }
                }
            }*/

            if (contain) {
                System.out.println("NG");
                continue;
            }
            System.out.println("OK");
        }
    }
}