算法思路

本题要求验证输入的密码是否符合特定条件。我们需要按照题目要求进行以下验证：

  1. 长度验证：密码长度必须大于 8。
  2. 字符种类验证：密码至少包含以下四种字符中的三种：
    • 大写字母 (A-Z)。
    • 小写字母 (a-z)。
    • 数字 (0-9)。
    • 其他符号（不包含空格和换行符）。
  3. 重复子串验证：密码不能包含长度大于 2 的相同子串。

根据这些规则，我们逐一进行验证，若某一规则不满足，则输出 NG；如果所有规则均满足，输出 OK。

Code

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    while (true) {
        const input = await readline();
        if (!input) break;

        // 1. 检查长度
        if (input.length <= 8) {
            console.log("NG");
            continue;
        }

        // 2. 检查字符种类
        let types = 0; // 字符种类计数
        if (/[A-Z]/.test(input)) types++; // 包含大写字母
        if (/[a-z]/.test(input)) types++; // 包含小写字母
        if (/\d/.test(input)) types++;   // 包含数字
        if (/[^A-Za-z0-9]/.test(input)) types++; // 包含其他符号

        if (types < 3) {
            console.log("NG");
            continue;
        }

        // 3. 检查重复子串
        let hasDuplicate = false;
        for (let i = 0; i < input.length - 2; i++) {
            const subStr = input.slice(i, i + 3); // 长度为3的子串
            if (input.indexOf(subStr, i + 3) !== -1) {
                hasDuplicate = true;
                break;
            }
        }

        if (hasDuplicate) {
            console.log("NG");
        } else {
            console.log("OK");
        }
    }
}();

复杂度分析

  1. 时间复杂度：
    • 长度验证：O(1)。
    • 字符种类验证：每种类型检查需要遍历字符串一次，总共 4 次，时间复杂度为 O(n)。
    • 重复子串验证：对每个长度为 3 的子串进行搜索，时间复杂度为 O(n²)。
    • 总体时间复杂度：O(n²)，其中 n 是字符串长度。
  2. 空间复杂度：
    • 仅使用了常量级变量来计数或保存子串，没有额外的数据结构，空间复杂度为 O(1)。