解题思路

1. 统计字符类型数量

首先遍历密码字符串，统计四类字符的出现次数：

大写字母（i1）、小写字母（i2）、数字（i3）、特殊符号（i4）。

2. 标记 “唯一类” 字符

若某类字符的出现次数为 1，则该类为 “唯一类”：

替换唯一类的字符时，只能选择同类其他字符（否则会导致该类型缺失，违反合法密码要求）；
用布尔数组 arr 标记每类是否为唯一类（arr[ch]=true 表示第 ch 类是唯一类）。

3. 计算每个字符的合法替换数

遍历每个字符，根据其所属类型是否为唯一类，计算合法替换方案数：

若为唯一类：大写字母（26 种）：可替换为其他 25 种大写字母；小写字母（26 种）：可替换为其他 25 种小写字母；数字（10 种）：可替换为其他 9 种数字；特殊符号（4 种）：可替换为其他 3 种特殊符号；
若不为唯一类：合法字符总数为 26+26+10+4=66 种，排除原字符本身，可替换为 65 种字符。

4. 累加总方案数

将每个字符的合法替换数累加，得到最终的总方案数。

ACnode

#include <bits/stdc++.h>
using namespace std;
#define int long long//防止溢出
#define endl '\n'

void solve()
{
    string s;
    cin >> s;
    // 统计四类字符的数量：i1=大写字母，i2=小写字母，i3=数字，i4=特殊符号
    int i1 = 0, i2 = 0, i3 = 0, i4 = 0;
    for (char c : s)
    {
        if (isupper(c))
            i1++;
        else if (islower(c))
            i2++;
        else if (isdigit(c))
            i3++;
        else
            i4++; 
    }

    // 标记每类是否数量为1
    vector<bool> arr(4, false);
    if (i1 == 1)
        arr[0] = true; // 大写字母
    if (i2 == 1)
        arr[1] = true; // 小写字母
    if (i3 == 1)
        arr[2] = true; // 数字
    if (i4 == 1)
        arr[3] = true; // 特殊符号

    int ans = 0; 
    for (char c : s)
    {
        // 确定当前字符所属类型（0=大写，1=小写，2=数字，3=特殊符号）
        int ch;
        if (isupper(c))
            ch = 0;
        else if (islower(c))
            ch = 1;
        else if (isdigit(c))
            ch = 2;
        else
            ch = 3;

        // 根据是否为唯一类计算合法替换数
        if (arr[ch])
        {
            // 唯一类：只能替换为同类其他字符（排除原字符）
            if (ch == 0)
                ans += 25; // 大写字母：26-1=25种选择
            else if (ch == 1)
                ans += 25; // 小写字母：26-1=25种选择
            else if (ch == 2)
                ans += 9;  // 数字：10-1=9种选择
            else
                ans += 3;  // 特殊符号：4-1=3种选择
        }
        else
        {
            // 合法字符总数=26+26+10+4=66，66-1=65种选择
            ans += 65;
        }
    }
    cout << ans << '\n';
}

signed main()
{
    // 关闭同步，加速输入输出
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int qwq;
    cin >> qwq; 
    while (qwq--)
    {
        solve(); // 处理每组
    }
    return 0;
}

时间与空间复杂度分析

一、时间复杂度

整体复杂度：O(t * n)，其中 t 为测试用例数，n 为单个密码字符串的长度

1. 单组测试用例的时间消耗

对于每组测试用例，代码执行两个核心遍历操作：

第一遍遍历（字符类型统计）：遍历密码字符串的每个字符，统计四类字符（大写字母、小写字母、数字、特殊符号）的数量。遍历次数为字符串长度 n，每个字符的判断操作（isupper/islower/isdigit）均为 O(1)时间复杂度，因此这部分耗时为 O(n)。
第二遍遍历（方案数计算）：再次遍历字符串的每个字符，根据字符所属类型是否为唯一类，累加合法替换方案数。同样遍历次数为 n，每个字符的类型判断、方案数计算均为 O(1) 操作，因此这部分耗时也为 O(n)。

两组遍历独立且无嵌套，单组测试用例的总时间复杂度为 O(n) + O(n) = O(n)。

2. 多组测试用例的时间叠加

题目中测试用例数最大1e5，且每个密码字符串的长度 n 满足8-16。由于 n 是固定范围的常数（最大仅 16），可将 O(n) 简化为 O(1)，因此整体时间复杂度可进一步优化为 O(t)

题解 | 小红的密码修改