C++字符串替换：用标记数组实现重复字母替换的完整指南

最近在牛客网刷字符串题，总是绕不开“字符串替换”这类看起来毫无难度的题目。题目描述通常很简单：给定一个字符串，把其中重复出现的字母替换成'#'，第一次出现的字母保持不变。乍一看谁都会，可真用 C++ 动手写的时候，问题会一串一串冒出来：大小写算不算重复？数字和标点要不要管？空格怎么读进来？数组下标怎么会是负数？这篇文章不打算只贴一段代码就交差，我会把这道题从题意拆解到多种 C++ 实现，再到常见踩坑点，完整走一遍。无论你是刚学完 C++ 语法的小白，还是准备面试想快速过一遍基本功的人，都可以顺着这里的思路自己敲一遍，把字符串处理的基础打扎实。

1. 题目理解与整体设计思路

1.1 题意还原：到底要对字符串做什么

牛客网上的“字符串替换”题，不同版本细节略有差别，但核心规则基本一致：把字符串中首次出现的字母保留，之后再次出现的相同字母统一替换为字符'#'。注意这里的关键词是“相同字母”，不是“相同字符”。如果题目只限定字母，那数字、空格、标点符号都应该原样保留。

把需求拆开看，实际上要做两件事。第一，遍历字符串的每一个字符，判断它是不是需要被处理的字母；第二，判断这个字母在当前位置之前是否已经出现过，如果出现过就改成'#'，否则记录一下“这个字母已经出现了”。整个过程不需要对字符串做移位、不需要删除元素、不需要拼接新串，只是做一次“边扫描边修改”的操作。

这道题之所以经典，是因为它把几个基础能力揉在一起：字符遍历、ASCII 码的数值运算、用数组做标记、以及原地修改字符串。很多更复杂的字符串题，比如统计字符频率、判断字符是否重复、滑动窗口去重，底层都会用到类似的思路。所以把这道题吃透，比多刷十道简单字符串题都值。

1.2 为什么“标记数组”是这道题的天然选择

我第一次刷这道题的时候，脑子里冒出来的想法很朴素：每遇到一个字母，就往回扫描一遍，看前面有没有出现过。比如字符串"abcabc"，处理第4个字母'a'时，需要回头看前3个字符里有没有'a'。这么做当然也能跑，但如果字符串长度是 n，最坏情况下每个字符都要往回扫 n 次，时间复杂度退化到 O(n²)，这就不是一个让人满意的解法。

后来意识到，题目要求的是“这个字母之前有没有出现过”，天然适合用一个数组记录状态。因为英文字母一共就26个（小写）或52个（分大小写），我们可以开一个固定大小的数组，数组下标对应字母编号，数组的值标记“这个字母是否已经出现”。遍历字符串时，先查标记数组，如果是第一次出现就置为1，否则就把当前字符替换成'#'。

用生活里的场景类比，这就像酒店前台登记入住的客人。前台小姐姐拿一份名单，来一位客人先查名单：没登记过，就在名单上打个勾然后放行；已经登记过了，就告诉他“您已经来过了，请去门牌号为#的房间”。整个流程只要扫一遍客人列表，不需要每次都回头问前面的客人。这就是典型的空间换时间：用一个固定大小数组的 O(1) 空间，换来了 O(n) 的线性时间复杂度。

1.3 两个容易混淆的规则：大小写与字符范围

动手写代码之前，必须先把题目规则确认清楚，否则写完了也是白写。我遇到过两个最容易出问题的点。

第一个是大小写是否区分。有的题目认为 'a' 和 'A' 是同一个字母，也就是大小写不敏感；有的题目则认为它们是两个字符，必须分开统计。如果题目描述里写“相同的字母”，通常要看看样例再判断。比如相同输入"aA"，不区分大小写的输出是"a#"，区分大小写的输出是"aA"，两个人答案完全不同，测试点直接判错。

第二个是替换范围。题目到底是说“把重复出现的字母替换成#”，还是“把重复出现的字符替换成#”？前者只处理 a-z 和 A-Z，遇到数字、空格、标点一律跳过；后者范围就广了，所有可见字符包括数字、空格都可能被替换。我见过不少人在这一点上栽跟头，明明题目只说字母，结果代码里把空格也处理了，输出自然不对。

所以在读题阶段，我建议先把这两点圈出来，再动手写思路。牛客网有些题的描述写得比较简略，实在拿不准的时候，用题目给出的样例去推断规则，或者直接按最常见的“只处理字母、大小写不敏感”来写，并在注释里写明你的假设。

2. 核心细节解析与 C++ 实现要点

2.1 ASCII 映射原理：字符和数组下标是怎么换算的

C++ 里的字符类型 char 本质上是一个占用1字节的整数，存储的是该字符在 ASCII 编码表中对应的数值。比如小写字母 'a' 的 ASCII 码是97，'z' 是122；大写字母 'A' 是65，'Z' 是90。这意味着我们可以拿字符直接做算术运算，把字母映射到数组下标。

具体来说，s[i] - 'a'会把一个小写字母映射到 0 到 25 之间的整数，'a' 映射到0，'b' 映射到1，以此类推。同理，s[i] - 'A'可以把大写字母映射到0到25。有了这个映射，标记数组就能设计成int seen[26]，每个位置对应一个字母。

如果题目是大小写不敏感，大写和小写字母应该复用同一个下标。常见做法是先把字符统一转成小写再减 'a'，或者在小写分支用s[i] - 'a'，在大写分支用s[i] - 'A'，因为这两个计算对同一个字母得到的结果是一样的。例如'l' 和 'L' 都会映射到下标11，所以后面的'l' 或 'L' 都会被当作重复字母处理。

这里有个非常容易出现的问题：如果不对字符做范围判断，直接拿一个字符去减 'a'，有可能得到负数或者超过25的整数。比如拿空格（ASCII 码32）减97，结果是 -65，用它做数组下标访问seen[-65]，程序运行时会访问到数组之外的内存，轻则结果错误，重则直接崩溃。所以进行下标换算之前，必须先确认ch >= 'a' && ch <= 'z'或者ch >= 'A' && ch <= 'Z'。

2.2 C 风格数组和 std::string 两种载体怎么选

牛客网上的老题，很多保留了 C 语言风格的输入输出方式，char 数组可以直接配合 scanf、printf 使用，修改也直观。C 风格数组的写法会更靠近底层，适合想复习指针和数组基本功的读者。

#include <stdio.h> #include <string.h> void replaceString(char* s) { int len = strlen(s); int seen[26] = {0}; for (int i = 0; i < len; ++i) { if (s[i] >= 'a' && s[i] <= 'z') { int idx = s[i] - 'a'; if (seen[idx]) { s[i] = '#'; } else { seen[idx] = 1; } } else if (s[i] >= 'A' && s[i] <= 'Z') { int idx = s[i] - 'A'; if (seen[idx]) { s[i] = '#'; } else { seen[idx] = 1; } } } } int main() { char s[100] = {0}; scanf("%s", s); replaceString(s); printf("%s\n", s); return 0; }

std::string 则更符合现代 C++ 的写法，用 getline 可以很方便地读取包含空格的整行输入，遍历和修改也简洁。牛客的在线评测环境一般支持 C++11 或 C++14，使用 std::string 完全没有问题。

#include <iostream> #include <string> using namespace std; void replaceString(string& s) { int seen[26] = {0}; for (char& c : s) { if (c >= 'a' && c <= 'z') { int idx = c - 'a'; if (seen[idx]) c = '#'; else seen[idx] = 1; } else if (c >= 'A' && c <= 'Z') { int idx = c - 'A'; if (seen[idx]) c = '#'; else seen[idx] = 1; } } } int main() { string s; getline(cin, s); replaceString(s); cout << s << endl; return 0; }

我个人的建议是，两种写法都要会。如果目标是把题目快速 AC，用自己最熟的那一种就好；如果是想锻炼 C++ 功底，就刻意把两种都写一遍，感受一下指针遍历、迭代器遍历、范围 for 循环之间的差异。

2.3 原地修改字符串的边界问题

这道题通常要求修改原字符串并输出，而不是生成一个新的字符串返回。所以我们要直接在传入的字符数组或 string 对象上进行操作。原地修改有几个细节值得注意。

第一，不能用字符串字面量作为输入。比如const char* p = "abcabc";这种写法在 C++ 里是一个只读的字符串常量，往p[3]写值属于未定义行为，程序可能崩溃。牛客的输入一般是先读到 char 数组里，数组是可写的，所以这一步通常没问题。但如果自己本地测试，千万别用字符串字面量去替代可写数组。

第二，替换成 '#' 不会截断字符串。因为 '#' 的 ASCII 码不是0，替换之后只是把原来的字母变成了井号，字符串的结尾符 '\0' 还在原来的位置，所以打印时能正常输出完整内容。这里要小心，别把第一次出现的字母误改成 '\0'，那样字符串会被提前截断，输出就少了一段。

第三，string 对象在修改时长度不会变化，因为我们只是逐字符替换，不涉及插入、删除，所以迭代器不会失效。但要注意，在 C++ 里对 string 使用下标访问时，最好先把长度存下来，避免每次循环都调用 size() 方法，虽然这点性能损耗在这道题里几乎可以忽略，但养成好习惯总没错。

3. 实操过程与核心环节实现

3.1 基础实现：只处理字母，大小写不敏感

先给一个贴合牛客常见题意的版本：只处理英文字母，大小写不敏感，非字母字符原样保留。代码的思路很清晰，单个循环就能完成。

#include <stdio.h> #include <string.h> void replaceString(char* s) { int len = strlen(s); int seen[26] = {0}; for (int i = 0; i < len; ++i) { if (s[i] >= 'a' && s[i] <= 'z') { int idx = s[i] - 'a'; if (seen[idx]) { s[i] = '#'; } else { seen[idx] = 1; } } else if (s[i] >= 'A' && s[i] <= 'Z') { int idx = s[i] - 'A'; if (seen[idx]) { s[i] = '#'; } else { seen[idx] = 1; } } } } int main() { char s[100] = {0}; scanf("%s", s); replaceString(s); printf("%s\n", s); return 0; }

这个版本里有几个刻意设计的点。首先，seen[26]声明为 int 数组，值是0或1，用来表示某个字母是否出现过。其次，大写和小写字母共用同一个 seen 数组，这就是大小写不敏感的实现方式。最后，else if 的写法保证每个字符只进入一个分支，字符本身就是大写或小写之一，不会同时处理两次。

提示：如果你不确定题目是否区分大小写，可以先用这个大小写不敏感的版本提交看看，如果某些测试点没过，再改成区分大小写的版本。根据我在牛客上的经验，很多字符串替换题确实是大小写不敏感的，但一定要以题目样例为准。

3.2 进阶实现：用 ASCII 码作下标的通用去重写法

如果题目要求不是“只处理字母”，而是“把所有重复出现的字符都替换为#”，那么开一个bool seen[128]会更合适。直接用字符的 ASCII 码作为数组下标，数字、标点、字母统统可以被记录，代码更短，思路也更通用。

#include <stdio.h> #include <string.h> void replaceString(char* s) { int seen[128] = {0}; int len = strlen(s); for (int i = 0; i < len; ++i) { unsigned char ch = (unsigned char)s[i]; if (seen[ch]) { s[i] = '#'; } else { seen[ch] = 1; } } } int main() { char s[100] = {0}; scanf("%s", s); replaceString(s); printf("%s\n", s); return 0; }

注意到这里用了unsigned char类型转换。之所以这样做，是因为某些平台上的 char 类型默认是 signed，当字符串中出现 ASCII 码大于127的扩展字符时，s[i]作为数组下标可能是负数，导致访问越界。转成 unsigned char 后，下标范围能正确覆盖 0 到 255。虽然牛客的普通测试一般不会出现扩展字符，但写成这样更稳。

同样地，std::string 版本也可以用同样的思路，配合getline读取可能有空格的整行字符串。

#include <iostream> #include <string> using namespace std; int main() { string s; getline(cin, s); int seen[128] = {0}; for (int i = 0; i < (int)s.size(); ++i) { unsigned char ch = (unsigned char)s[i]; if (seen[ch]) { s[i] = '#'; } else { seen[ch] = 1; } } cout << s << endl; return 0; }

有的同学可能会想用std::map或者std::set来做，但这道题完全没有必要。map 内部是红黑树，插入和查找的时间复杂度是 O(log n)，性能不如数组；unordered_set 虽然平均 O(1)，但哈希函数有额外开销。定长数组是最轻量、最直接的选择，这也算是一种“在合适场景选择合适的工具”的思维方式。

3.3 测试用例与输出对比

写完代码不能直接交，一定要自己构造几组用例测一测。针对不同的题目规则，我列了一张对比表，方便你看清楚规则差异会造成什么影响。

以"Hello World"为例，不区分大小写时，第一个 l 保留，后面的 l 和 L 如果出现都会被替换，大写 W 因为是第一次出现所以保留，后面再次出现的 o 会被替换成 #。而区分大小写时，小写 o 和大写 O 互不影响，所以第二组结果不同。

这些用例在本地跑通之后，再提交到牛客网，心里就有底了。我习惯在本地多写几组极端用例，比如长度只有1的字符串、全是同一个字母的字符串、字母夹杂数字的字符串，比直接提交然后靠评测结果反馈要高效得多。

3.4 复杂度分析和优化空间

这道题的时间复杂度很容易分析：只需要从头到尾遍历一次字符串，每次循环内做常数次判断和数组访问，所以是 O(n)，n 是字符串长度。空间复杂度方面，标记数组是固定大小，不随输入规模变化，所以是 O(1)。如果硬要计算，char 数组本身是题目输入的一部分，不算额外空间。

那么还有没有优化空间？从复杂度上看，已经没有什么可优化的了。任何“判断重复”的问题都至少需要扫描一遍输入，否则无法知道后面的字符在之前是否出现过。所以 O(n) 时间、O(1) 额外空间的解法就是这个问题的理论最优解。

不过，代码层面还有可以微调的地方。如果你写的是 C 风格版本，可以尝试用指针遍历代替数组下标遍历，比如char* p = s; while (*p) { ... ++p; }，这样能少一次strlen的扫描，因为你是边移动指针边判断是否到结尾。对这道题来说，这个优化收益微乎其微，但作为 C 语言功底的练习，值得试试。如果你用的是 std::string，也可以试试用迭代器或者范围 for 循环，感受不同遍历方式写起来有什么区别。

4. 常见问题与排查技巧实录

4.1 输入方式不对，导致字符串只处理了一半

这是我在牛客评论区里见过最多的问题。很多新手用scanf("%s", s)读字符串，如果测试数据里包含空格，比如"Hello World"，scanf 只读到"Hello"就停住了，空格和后面的"World"都留在缓冲区里，代码处理的实际上是"Hello"。

解决思路要看具体情况。如果题目保证输入不含空格，那scanf("%s", s)简单又高效。如果输入可能包含空格，C 语言可以用scanf("%[^\n]", s)来读取一整行，或者用cin.getline(s, 100)。std::string 的话，直接用getline(cin, s)最合适。

注意：gets函数在 C++11 标准里已经被移除了，牛客的编译器如果用 C++11 或更高版本，提交包含gets的代码很可能编译失败。老旧教材里经常出现gets，刷题时建议改用fgets或cin.getline。

4.2 非字母字符被错误替换，结果和答案对不上

如果题目只说“把重复出现的字母替换成#”，那么代码里必须对字符做范围判断。我见过直接把seen[128]方案用在“只处理字母”题目上的读者，结果空格、数字也全变成 # 了，输出自然不对。

反过来，如果题目说“把重复出现的字符都替换成#”，那你只需要判断字符是否出现过，不需要关心它是不是字母。最稳妥的办法是读题时把“字母”两个字圈出来，代码里写成if (s[i] >= 'a' && s[i] <= 'z')或者if (s[i] >= 'A' && s[i] <= 'Z')这样的范围判断。

4.3 数组越界、野指针和运行时错误

这道题虽然简单，但运行时错误（RE）并不少见。最常见的原因是直接拿字符减 'a' 得到的下标是负数，然后访问了数组的越界位置。比如输入一个数字 '1'，它的 ASCII 码是49，49 - 97 = -48，访问 saw[-48] 就会出事。

排查这类问题，我一般先打印每个字符的 ASCII 码，看看程序实际处理的数据长什么样。比如临时在循环里加一句printf("%d %c\n", s[i], s[i]);，一旦发现某个字符在做减法之前没有满足字母判断条件，问题就定位了。另一个技巧是使用 vector 的at()方法访问元素，它会在越界时抛出异常，方便本地调试；定位完再改回数组下标即可。

还有一种情况是字符串数组开得太小。牛客的题目如果没说明长度限制，你可以预估一下，但保险起见开char s[1000]甚至更大的长度，避免读入数据超过数组大小。如果你用 std::string 就不存在这个问题，这也是我推荐在刷题时多用 string 的原因之一。

4.4 牛客网提交的几个实际细节

牛客网的在线评测环境和本地 IDE 有些细微差别，提交通常需要注意几点。第一，main 函数最后要return 0;，很多新手会漏掉，虽然某些编译器能过，但最好还是按标准写。第二，如果题目要求“多组测试数据”，不要只处理一组就返回，需要使用 while 循环不断读入，直到输入结束。第三，尽量不要依赖#include <bits/stdc++.h>这个万能头文件，虽然牛客支持，但它不是标准头文件，换到其他平台可能编译失败，老老实实包含<iostream>、<string>、<stdio.h>更稳妥。

还有一个经验之谈：提交后如果答案错误，别急着改代码逻辑，先看错误用例。牛客有些题目会在“错误提示”里给出你输出和期望输出的对比，这是最快的定位方式。如果只显示“答案错误”而没有用例，那就自己多造几组边界测试，比如全重复、无重复、空字符串、大小写混合，逐一验证。

最后分享一个我从这道题里得到的习惯：刷题时不要只看代码能不能过，而是要有意识地把同一个问题用不同方法各写一遍。字符串替换这道题，用 C 风格数组写一遍，再用 std::string 写一遍，然后变形成“大小写敏感”和“所有重复字符”的版本，总共只需要半小时左右，但你会对字符判断、标记数组、输入读取这些基础能力产生肌肉记忆。下次再遇到“判断字符是否重复”“统计字符频率”之类的题，你会在第一时间想到这棵技能树，这就是把简单题吃透的价值。