小美的密码

[题目链接](https://www.nowcoder.com/practice/e95f6a9dec8242cbb3a0ca24ab98e8be)

思路

小美有 $n$ 个候选密码，她会按照长度从小到大的顺序依次尝试，相同长度的密码随机尝试，且相同的密码只尝试一次。问最少和最多各需要尝试多少次。

分析

由于尝试顺序是按长度从小到大的，所以：

所有长度比正确密码短的候选密码一定会先被尝试完；
在与正确密码等长的那一组中，由于顺序随机，正确密码可能第一个被尝试（最好情况），也可能最后一个被尝试（最坏情况）。

设去重后，长度比正确密码短的候选密码共 $\text{before}$ 个，与正确密码等长的候选密码共 $\text{same}$ 个，则：

$ $\text{最少尝试次数} = \text{before} + 1$ $

$ $\text{最多尝试次数} = \text{before} + \text{same}$ $

实现步骤

读入正确密码和所有候选密码；
对候选密码去重；
按长度统计每组有多少个不同的密码；
累加所有长度小于正确密码长度的组的密码数，得到 $\text{before}$ ；
取与正确密码等长的组的密码数，得到 $\text{same}$ ；
输出 $\text{before} + 1$ 和 $\text{before} + \text{same}$ 。

样例演示

输入中候选密码为 ["abc", "ab", "ac", "ac"]，正确密码为 "ab"。

去重后为 ["abc", "ab", "ac"]。按长度分组：

长度 2："ab", "ac"（共 2 个）
长度 3："abc"（共 1 个）

正确密码 "ab" 的长度为 2，没有更短的密码，所以 $\text{before} = 0$ ， $\text{same} = 2$ 。

$ $\text{最少} = 0 + 1 = 1, \quad \text{最多} = 0 + 2 = 2$ $

输出 1 2。

复杂度分析

时间复杂度： $O(n \cdot L)$ ，其中 $L$ 是密码的平均长度，主要开销在字符串去重（哈希集合操作）。
空间复杂度： $O(n \cdot L)$ ，存储去重后的密码集合。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    string correct;
    cin >> correct;

    set<string> seen;
    map<int, int> lenCount;

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        if (seen.insert(s).second) {
            lenCount[s.size()]++;
        }
    }

    int correctLen = correct.size();
    int before = 0;
    for (auto& [len, cnt] : lenCount) {
        if (len < correctLen) {
            before += cnt;
        }
    }

    int sameGroup = lenCount[correctLen];
    cout << before + 1 << " " << before + sameGroup << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String correct = sc.next();

        Set<String> seen = new HashSet<>();
        Map<Integer, Integer> lenCount = new TreeMap<>();

        for (int i = 0; i < n; i++) {
            String s = sc.next();
            if (seen.add(s)) {
                lenCount.merge(s.length(), 1, Integer::sum);
            }
        }

        int correctLen = correct.length();
        int before = 0;
        for (Map.Entry<Integer, Integer> e : lenCount.entrySet()) {
            if (e.getKey() < correctLen) {
                before += e.getValue();
            }
        }

        int sameGroup = lenCount.getOrDefault(correctLen, 0);
        System.out.println((before + 1) + " " + (before + sameGroup));
    }
}