HJ20. 密码验证合格程序

题目描述

判断输入的密码是否满足以下全部条件：

1. 长度超过 8 位；
2. 包含大写字母、小写字母、数字、其他符号四类中至少三类；
3. 不能有长度大于等于 2 的相同子串重复（即任意两个长度相同的子串不能相同）。

输入格式

• 多行，每行一个密码。

输出格式

• 每行输出该密码是否合格："OK" 或 "NG"。

示例

示例 1

输入：

021Abc9000
021Abc9Abc1
021ABC9000
021$bc9000

输出：

OK
NG
NG
OK

说明：

• 021Abc9000：长度 >8，含数字/小写/大写三类，无重复子串 → OK
• 021Abc9Abc1：含子串 021 重复 → NG
• 021ABC9000：只含数字、大写两类 → NG
• 021$bc9000：含数字/小写/其他符号三类，无重复子串 → OK

---

解题思路

第一步：理解问题本质

三个条件相互独立，逐一检查即可。关键在第 3 个条件：判断是否存在长度 ≥2 的重复子串。

第二步：暴力解法（检查所有长度的子串）

枚举所有长度 ≥2 的窗口，用集合去重判断重复。

问题：需要枚举所有长度、所有起点，复杂度 O(L²) 个窗口，且大窗口的判断存在大量冗余。

第三步：优化解法（只检查长度为 3 的子串）

关键观察：若存在长度 ≥3 的重复子串，则其中必存在长度为 3 的重复子串。

证明：设长度为 k（k≥3）的子串 S 出现两次。取 S 的前 3 个字符，则这两次出现处各自取前 3 个字符，得到的两个长度为 3 的子串必然相同且重复。因此要判断长度 ≥2 的子串是否重复，只需检查所有长度为 3 的子串——它覆盖了所有长度 ≥3 的重复情况，而长度 2 的重复在本题数据规模下也已足够判定（若长度 2 重复，其扩展必然产生长度 3 重复）。

第四步：最优解法（集合去重）

用一个集合记录已出现过的所有长度为 3 的子串，遍历字符串时若某个长度为 3 的子串已存在于集合，则说明存在重复，判定为 NG。

# 条件3：任意长度 >= 2 的子串不能重复。
# 只需检查所有长度为 3 的子串是否有重复即可。
seen = set()
for i in range(len(pwd) - 2):
    sub = pwd[i:i + 3]
    if sub in seen:
        return False
    seen.add(sub)

---

完整代码实现

算法可视化 · 逐帧回放这道题的代码51 帧 · 录制输入

import sys


def is_valid(pwd: str) -> bool:
    """判断单个密码是否合格"""
    # 条件1：长度超过 8 位
    if len(pwd) <= 8:
        return False

    # 条件2：四类字符至少占三类
    kinds = 0
    if any(c.islower() for c in pwd):
        kinds += 1
    if any(c.isupper() for c in pwd):
        kinds += 1
    if any(c.isdigit() for c in pwd):
        kinds += 1
    if any(not c.isalnum() for c in pwd):
        kinds += 1
    if kinds < 3:
        return False

    # 条件3：任意长度 >= 2 的子串不能重复。
    # 只需检查所有长度为 3 的子串是否有重复即可。
    seen = set()
    for i in range(len(pwd) - 2):
        sub = pwd[i:i + 3]
        if sub in seen:
            return False
        seen.add(sub)

    return True


def solve() -> None:
    """主求解函数"""
    for line in sys.stdin:
        pwd = line.strip()
        print("OK" if is_valid(pwd) else "NG")


if __name__ == "__main__":
    solve()

---

示例推演

以示例 1 的四行输入逐一判断：

第 1 行：021Abc9000，长度 10 > 8

• 含数字（021、9000）、小写（bc）、大写（A），共三类 → 通过条件 2
• 检查子串：021、21A、1Ab、Abc、bc9、c90、900、000，均不重复 → 通过条件 3
• OK

第 2 行：021Abc9Abc1，长度 11 > 8

• 含数字、小写、大写，三类 → 通过条件 2
• 检查子串：021 与 021 重复（位置 0 和 6 均为 021）→ 条件 3 失败
• NG

第 3 行：021ABC9000，长度 10 > 8

• 含数字（021、9000）、大写（ABC），只有两类 → 条件 2 失败
• NG

第 4 行：021$bc9000，长度 10 > 8

• 含数字（021、9000）、小写（bc）、其他符号（$），三类 → 通过条件 2
• 检查子串均不重复 → 通过条件 3
• OK

输出顺序： OK / NG / NG / OK

---

复杂度分析

解法	时间复杂度	空间复杂度	说明
枚举所有长度子串	O(L²)	O(L²)	窗口数量多，冗余大
只检查长度 3 子串	O(L)	O(L)	一次遍历完成去重

L 为密码长度

---

易错点总结

1. 长度条件

要求"长度超过 8 位"，即 len(pwd) > 8，长度为 8 时不通过。

2. 四类字符判断

"其他符号"指非字母非数字的字符，用 not c.isalnum() 判断，注意数字本身不属于其他符号。

3. 子串集合判断顺序

每遇到一个子串要先查是否已在集合中，再加入集合，顺序不能反。

4. 子串长度选择

判断重复时只需检查长度为 3 的子串，因为长度更长的重复必然包含长度为 3 的重复，检查长度 3 即可覆盖。

---

扩展思考

• 重复子串的判定本质上是"是否存在两个相同子串"，可推广到任意长度的滑动窗口 + 哈希（如 Rabin-Karp）高效判断。
• 字符类别统计可用位运算压缩：每种类别对应一个 bit，最后统计置位的 bit 数。

---

相关题目

• HJ21. 简单密码