遍历列表匹配HONI顺序字符 代码逻辑错误及TLE问题排查

题目规则 #

• 输入为大写字母组成的字符串，统计按严格顺序依次出现H、O、N、I的完整轮次总次数
• 匹配规则要求仅从字符串头到尾单次遍历，不涉及组合、排列计算：
  • 找到第一个H后，忽略该位置到下一个待匹配字符之间的所有字符（即使是目标字符也跳过）
  • 在H之后找第一个出现的O，找到O后继续在其后找第一个N，找到N后在其后找第一个I
  • 完成一次H-O-N-I匹配则计数加1，之后从I的下一个位置重复上述匹配流程

故障现象 #

• 提交代码后前6个测试用例通过，剩余5个测试用例全部失败
• 测试结果返回TLE（时间超限）提示，自行构造测试用例始终无法复现错误

官方样例 #

• 输入HHHHOOOONNNNIIII，输出1
• 输入PROHODNIHODNIK，输出2
• 输入HONIIONIHHONI，输出2
• 输入HONIHONIHONI，输出3
• 输入HOHONINI，输出1
• 输入HIONHION，输出1

原有实现代码 #

# DMOJ problem coci18c3p1
lst = list(input().upper())

if not 1 <= len(lst) <= 100000:
    print(0)
    raise SystemExit

filtered = [x for x in lst if x in 'HONI']
# print(filtered)

letters = 'H', 'O', 'N', 'I'

if any(i not in filtered for i in letters):
    print(0)
    raise SystemExit

count = 0

while True:
    if 'H' not in filtered:
        break
    h = filtered.index("H")
    count += 1
    if h != 0:
        filtered = filtered[h:]

    if 'O' not in filtered:
        break
    o = filtered.index("O")
    count += 1
    if o != 0:
        filtered = filtered[o:]

    if 'N' not in filtered:
        break
    n = filtered.index("N")
    count += 1
    if n != 0:
        filtered = filtered[n:]

    if 'I' not in filtered:
        break
    i = filtered.index("I")
    count += 1
    if i != 0:
        filtered = filtered[i:]

print(count//4)

问题根因 #

1. 逻辑错误 #

提前判断过滤后的列表是否包含全部H/O/N/I的逻辑完全不成立：只要字符串中凑齐过四个字母就会通过校验，但如果字符顺序不满足要求（比如所有I都出现在N之前），实际根本无法完成完整匹配，这部分判断属于多余逻辑，会直接导致部分顺序错误的用例返回错误结果。
另外计数逻辑也有冗余：每找到一个字符就给count加1最后整除4，完全可以找到完整一轮再计数，减少不必要的运算。

2. 效率问题导致TLE #

代码中反复使用in做成员判断、index()做查找、列表切片生成新列表，对于题目给出的1e5长度上限的输入，整体时间复杂度接近O(n²)，遇到连续重复字符多的极限用例很容易超时。

正确实现思路 #

只需要单次遍历字符串即可完成统计，时间复杂度O(n)，空间复杂度O(1)：

• 初始化待匹配目标序列为"HONI"，当前待匹配下标为0，最终计数为0
• 逐字符遍历输入字符串：
  • 如果当前字符等于待匹配序列的当前下标对应字符，将待匹配下标+1
  • 如果待匹配下标等于4，说明完成一轮完整匹配，计数+1，待匹配下标重置为0
• 遍历结束后直接输出计数即可，不需要额外过滤、切片、反复查找操作。

内容的提问来源于stack exchange，提问作者MarkS