ABC249B Perfect String

题意分析

给定一个字符串 $S$，我们需要判断该字符串是否满足以下三个条件：

1. 包含至少一个大写字母；
2. 包含至少一个小写字母；
3. 所有字符互不相同。

如果满足以上全部条件，输出 Yes，否则输出 No。

---

解题思路

本题实质是一个典型的字符串属性判断与计数问题，我们需要同时检查字符种类（大小写）和字符是否有重复。

步骤如下：

1. 遍历字符串，准备：

   • 一个布尔标记 has_upper 表示是否存在大写字母；
   • 一个布尔标记 has_lower 表示是否存在小写字母；
   • 一个布尔数组 vis[128] 用于记录字符是否出现过（适用于 ASCII 字符）。

2. 遍历每个字符 c：

   • 如果 c 是大写字母（'A'~'Z'），设置 has_upper = true；
   • 如果 c 是小写字母（'a'~'z'），设置 has_lower = true；
   • 判断字符 c 是否已经出现过：
     • 若已出现，说明字符不唯一，直接输出 No；
     • 否则标记该字符已出现。

3. 最后判断：

   • 若同时 has_upper、has_lower 都为 true，且没有重复字符，则输出 Yes；
   • 否则输出 No。

---

字符映射技巧回顾

为了高效判断某个字符是否出现过，可以使用一个 bool vis[128] 数组来记录每个 ASCII 字符的出现状态：

• vis[c] = true 表示字符 c 已经出现；
• 适用于所有常规可打印字符（ASCII 范围内）；
• 对于字母类字符也可使用 vis[26]，搭配 c - 'a' 或 c - 'A' 做映射。
  • 但本题既要存储大写字母又要存储小写字母，因此使用 vis[128] 会更方便。直接用 ASCII 码映射即可。

---

代码实现

#include <iostream>
using namespace std;
bool vis[128];
int main() 
{
    string s;
    cin >> s;
    bool has_upper = false;
    bool has_lower = false;
    for (int i = 0; i < s.size(); i++) 
    {
        char c = s[i];
        if (vis[c]) // 字符重复
        {
            cout << "No";
            return 0;
        }
        vis[c] = true;
        if (c >= 'A' && c <= 'Z') has_upper = true;
        if (c >= 'a' && c <= 'z') has_lower = true;
    }
    if (has_upper && has_lower) 
    {
        cout << "Yes";
    } 
    else 
    {
        cout << "No";
    }
    return 0;
}

---

时间与空间复杂度分析

• 时间复杂度：$O(N)$，$N$ 为字符串长度；
• 空间复杂度：$O(1)$，只需常数空间的布尔变量和标记数组。

---

总结

• 本题为字符串特性判断题；
• 涉及大小写字符判断、唯一性判断、计数统计；
• 关键是熟练运用字符映射与标记技巧。