题解 | 密码验证合格程序

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String s = sc.next();
            System.out.println(valid(s) ? "OK" : "NG");
        }
    }
    static boolean valid(String s) {
        // 长度匹配
        if (s.length() < 8) return false;
        // 字符数量合法性
        boolean up = false, low = false, dig = false, spec = false;
        for (char c : s.toCharArray()) {
            if (c >= 'A' && c <= 'Z') up = true;
            else if (c >= 'a' && c <= 'z') low = true;
            else if (c >= '0' && c <= '9') dig = true;
            else spec = true;
        }
        int types = 0;
        if (up) types++;
        if (low) types++;
        if (dig) types++;
        if (spec) types++;
        if (types < 3) return false;

        // 子串匹配 ！！
        int n = s.length();
        for (int len = 3; len * 2 <= n; len++) {
            Map<String, Integer> first = new HashMap<>();
            for (int i = 0; i + len <= n; i++) {
                String sub = s.substring(i, i + len);
                Integer prev = first.get(sub);
                if (prev != null) {
                    if (i >= prev + len) return false;
                } else {
                    first.put(sub, i);
                }
            }
        }
        return true;
    }


}