使用哈希表，时间复杂度O(n)

思路：

1. 条件一判断长度即可
2. 条件二针对四种情况使用四个变量分别标记，遍历完进行判断
3. 条件三使用哈希表保存子串和对应的起始下标，具体的：

• 如果哈希表不存在子串，说明不存在重复，直接保存
• 如果哈希表存在子串

1. 如果当前子串起始下标大于等于之前子串起始下标+3，说明是独立子串重复了，不符合条件
2. 否则说明子串虽然重复但是非独立，是符合条件的（这里不需要更新起始下标）

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String s = in.nextLine();
            if (isValid(s)) {
                System.out.println("OK");
            } else {
                System.out.println("NG");
            }
        }
    }

    private static boolean isValid(String s) {
        if (s.length() <= 8) {
            return false;
        }
        Map<String, Integer> map = new HashMap<>();
        int a = 0;
        int b = 0;
        int c = 0;
        int d = 0;
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch >= 'A' && ch <= 'Z') {
                a = 1;
            } else if (ch >= 'a' && ch <= 'z') {
                b = 1;
            } else if (ch >= '0' && ch <= '9') {
                c = 1;
            } else {
                d = 1;
            }
            if (i + 3 <= s.length()) {
                String t = s.substring(i, i + 3);
                if (!map.containsKey(t)) {
                    map.put(t, i);
                } else if (i >= map.get(t) + 3) {
                    return false;
                }
            }
        }
        return a + b + c + d >= 3;
    }
}