题意整理。

• 输入一行字符串密码，验证是否合法。
• 合法的密码需满足三个要求：1.长度大于8；2.包含大小写字母、数字、其它字符中至少三种；3.没有长度大于2的不含公共元素的重复子串。

方法一（模拟）

1.解题思路

• 写3个方法，分别判断是否满足对应的三个要求。
• 对于要求1，只需判断长度是否大于8。对于要求2，定义一个变量，记录对应字符的种类数目即可，然后判断种类数是否大于等于3。对于要求3，只需判断是否有长度为3的重复子串，因为有长度为3的重复子串，必定也会有长度超过3的重复子串。

图解展示（验证重复子串）：

2.代码实现

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            //输入密码
            String s=sc.nextLine();
            //如果三个要求都满足，输出“OK”
            if(matchlen(s)&&matchkind(s)&&matchsub(s)){
                System.out.println("OK");
            }
            //否则，输出“NG”
            else{
                System.out.println("NG");
            }
        }
        
    }
    //验证长度是否超过8
    private static boolean matchlen(String s){
        return s.length()>8;
    }
    //验证是否包含大小写字母、数字、其它字符中至少三种
    private static boolean matchkind(String s){
        //是否有大写字母
        boolean upper=false;
        //是否有小写字母
        boolean lower=false;
        //是否有数字
        boolean digit=false;
        //是否有其它字符
        boolean other=false;
        //用于统计字符种类数目
        int count=0;
        for(int i=0;i<s.length();i++){
            char c=s.charAt(i);
            if(c>='A'&&c<='Z'){
                upper=true;
            }
            else if(c>='a'&&c<='z'){
                lower=true;
            }
            else if(c>='0'&&c<='9'){
                digit=true;
            }
            else{
                other=true;
            }
            
        }
        if(upper){
            count++;
        }
        if(lower){
            count++;
        }
        if(digit){
            count++;
        }
        if(other){
            count++;
        }
        return count>=3;
    }
    //验证是否有长度大于2的不含公共元素的重复子串
    private static boolean matchsub(String s){
        for(int i=0;i<s.length()-3;i++){
            //截取长度为3的子串
            String temp=s.substring(i,i+3);
            //如果从i+3开始截取的子串包含temp，说明有重复
            if(s.substring(i+3).contains(temp)){
                return false;
            }
        }
        return true;
    }
}

3.复杂度分析

• 时间复杂度：对于matchlen方法，只需一次判读，时间复杂度为$O(1)O(1)$，对于matchkind方法，需要遍历字符串中所有字符，时间复杂度为$O(n)O(n)$,对于matchsub方法，需要遍历整个字符串，每次遍历中还有一个字符串截取操作，所以时间复杂度为$O(n^2)O(n^2)$，所以主函数的时间复杂度为$O(n^2)O(n^2)$。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度为$O(1)O(1)$。

方法二（利用io流）

1.解题思路

思路和方法一基本一致，不同的是通过io流操作来处理输入的数据。

2.代码实现

import java.io.*;

public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String s;
        while((s=br.readLine())!=null){
            //如果三个要求都满足，输出“OK”
            if(matchlen(s)&&matchkind(s)&&matchsub(s)){
                System.out.println("OK");
            }
            //否则，输出“NG”
            else{
                System.out.println("NG");
            }
        }
        
    }
    //验证长度是否超过8
    private static boolean matchlen(String s){
        return s.length()>8;
    }
    //验证是否包含大小写字母、数字、其它字符中至少三种
    private static boolean matchkind(String s){
        //是否有大写字母
        boolean upper=false;
        //是否有小写字母
        boolean lower=false;
        //是否有数字
        boolean digit=false;
        //是否有其它字符
        boolean other=false;
        //用于统计字符种类数目
        int count=0;
        for(int i=0;i<s.length();i++){
            char c=s.charAt(i);
            if(c>='A'&&c<='Z'){
                upper=true;
            }
            else if(c>='a'&&c<='z'){
                lower=true;
            }
            else if(c>='0'&&c<='9'){
                digit=true;
            }
            else{
                other=true;
            }
            
        }
        if(upper){
            count++;
        }
        if(lower){
            count++;
        }
        if(digit){
            count++;
        }
        if(other){
            count++;
        }
        return count>=3;
    }
    //验证是否有长度大于2的不含公共元素的重复子串
    private static boolean matchsub(String s){
        for(int i=0;i<s.length()-3;i++){
            //截取长度为3的子串
            String temp=s.substring(i,i+3);
            //如果从i+3开始截取的子串包含temp，说明有重复
            if(s.substring(i+3).contains(temp)){
                return false;
            }
        }
        return true;
    }
}

3.复杂度分析

• 时间复杂度：对于matchlen方法，只需一次判读，时间复杂度为$O(1)O(1)$，对于matchkind方法，需要遍历字符串中所有字符，时间复杂度为$O(n)O(n)$,对于matchsub方法，需要遍历整个字符串，每次遍历中还有一个字符串截取操作，所以时间复杂度为$O(n^2)O(n^2)$，所以主函数的时间复杂度为$O(n^2)O(n^2)$。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度为$O(1)O(1)$。