Moe's CF Life

喵~ 你好呀，各位Codelia的居民们！我是你们的小助手猫娘，今天也要元气满满地解决问题哦！

这次我们要看的题目是 C. Prepend and Append，一个关于字符串操作的小谜题。别担心，只要跟着我的思路，一下子就能明白啦，的说~

题目大意

这道题是这样的喵：

有一个叫 Timur 的人，他一开始有一个二进制字符串（就是只包含 '0' 和 '1' 的字符串，也可能是空的哦）。他可以对这个字符串进行一种神奇的操作，可以做好几次：

操作：在字符串的一端加上 '0'，同时在另一端加上 '1'。

举个例子喵，如果他一开始的字符串是 1011，他可以：

在左边加 '0'，右边加 '1'，变成 010111。
或者，在左边加 '1'，右边加 '0'，变成 110110。

现在呢，我们只知道 Timur 操作完之后的 最终字符串，题目想让我们找出，他一开始的 原始字符串 最短可能是多长。

解题思路

嘿嘿，这种“逆向工程”的问题，最有趣了！操作是往两边“加”东西，那我们想倒推回去，不就是把两边的东西“删掉”嘛~

我们来想一想，什么情况下可以“删掉”两端的字符呢？

根据操作的定义，每次操作都会在两端增加一个 '0' 和一个 '1'。这意味着，如果我们看到一个字符串的两端恰好是 一个 '0' 和一个 '1'（比如 0...1 或者 1...0），那它们就 有可能 是同一次操作加上去的。为了找到最短的原始字符串，我们应该尽可能多地撤销操作。所以，只要两端字符不同，我们就当它们是一次操作加上去的，然后把它们“删掉”，看看剩下的更短的字符串。

我们重复这个过程：

看看字符串最左边和最右边的字符。
如果它们不一样（一个是 '0'，一个是 '1'），那我们就认为这是一次操作的结果，把它们都“删掉”，然后对中间剩下的部分继续这个过程。
如果它们一样（都是 '0' 或者都是 '1'），那它们肯定不是同一次操作加上去的。这样我们就没法再“删掉”了，说明剩下的这部分就是最短的原始字符串的核心啦！

这个过程是不是听起来很适合用 双指针 来实现呀？我们可以用一个指针 left 指向字符串的开头，一个指针 right 指向字符串的结尾。

只要 left 还在 right 的左边，并且 s[left] 和 s[right] 不一样，我们就把 left 往右移一位，right 往左移一位，就像两只小猫爪子从两边向中间靠拢一样~
当 left 和 right 指向的字符相同时，或者两个指针相遇/交错时，这个过程就停下来。

最后剩下的 [left, right] 区间内的字符串，就是我们找到的最短的可能原始字符串啦！它的长度就是 right - left + 1。如果指针交错了（left > right），说明整个字符串都被我们“删”光了，原始字符串就是空的，长度为 0，这个公式算出来也正好是 0 或者负数，所以我们直接输出 right - left + 1 就好啦（当 left > right 时，结果小于等于 0，对于本题，最小长度是0，所以可以这么算）。

举个栗子：s = 1010110

left=0, right=6。s[0] 是 '1', s[6] 是 '0'。不一样！太好了，可以删掉。left 变成 1, right 变成 5。
现在看 s[1] 和 s[5]。s[1] 是 '0', s[5] 是 '1'。还是不一样！继续删。left 变成 2, right 变成 4。
现在看 s[2] 和 s[4]。s[2] 是 '1', s[4] 是 '1'。呀，它们一样！不能再删了。
停下来！剩下的部分是从 left=2 到 right=4 的子串 101。它的长度是 4 - 2 + 1 = 3。这就是答案啦~

代码解说

下面是 C++ 的实现代码，猫娘来给你逐行解释一下哦~

cpp

#include <iostream>
#include <string>
#include <algorithm>

// 这个函数用来解决单个测试用例，喵~
void solve() {
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;

    // 我们用双指针来找到最短的可能原始字符串~
    // 操作是在一端加 '0'，另一端加 '1'。
    // 要逆转这个操作，我们检查最外层的字符是不是不同的 ('0' 和 '1')。
    // 如果是，我们就可以通过向内移动指针来“移除”它们。
    // 我们一直重复这个过程，直到最外层的字符相同，或者指针相遇/交错。
    
    int left = 0;
    int right = n - 1;

    // 循环会一直进行，只要 left 指针在 right 指针的左边，
    // 并且它们指向的字符不同。
    while (left < right && s[left] != s[right]) {
        left++;
        right--;
    }

    // 剩下的子串（从索引 `left` 到 `right`）的长度就是答案。
    // 长度计算为 `right - left + 1`。
    // 这个公式可以完美处理所有情况：
    // 1. 如果循环因为 s[left] == s[right] 而停止，剩下的部分就是核心字符串。
    // 2. 如果指针相遇 (left == right)，还剩一个字符。长度是 1。
    // 3. 如果指针交错 (left > right)，整个字符串都被“约减”了。原始字符串是空的，长度是 0。
    //    比如，如果 left 变成 3，right 变成 2，长度就是 2 - 3 + 1 = 0。
    std::cout << right - left + 1 << "\n";
}

int main() {
    // 针对竞赛编程的快速 I/O 设置
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识点介绍

这道题虽然简单，但用到的思想可是很有用的哦！

双指针 (Two Pointers)
- 是什么？ 这是一种非常经典的算法技巧。它使用两个指针在数据结构（通常是数组或字符串）中移动，来解决问题。这两个指针可以从两端向中间移动，也可以都从一端开始以不同速度移动。
- 为什么好用？ 在这道题里，我们需要同时关注字符串的头部和尾部，双指针简直是为此量身定做的！它让我们可以在一次遍历（线性时间复杂度 O(n)）内就解决问题，非常高效。如果每次都真的去删除字符创建新字符串，那可就慢多啦！
- 其他应用场景：检查回文串、在有序数组中寻找和为定值的两个数、字符串反转等等，双指针的身影无处不在哦！
贪心算法 (Greedy Algorithm)
- 是什么？ 贪心算法就是在每一步选择中，都采取当前状态下最好或最优的选择，从而希望能导致全局最好或最优的解。
- 体现在哪里？ 我们的策略就是一种贪心。在每一步，只要我们可以通过删除两端不同的字符来缩短字符串，我们就立刻这么做。我们贪心地进行最多的“撤销操作”。在这个问题里，每次撤销操作都是独立的，并且总能让字符串变得更短，所以这种贪心策略恰好能得到正确的最优解。

好啦，这次的题解就到这里啦！是不是很简单呢？只要我们把问题反过来想，再用上双指针这个好用的小工具，问题就迎刃而解了。希望对你有帮助，喵~ 下次再见！

题目大意 ​

解题思路 ​

代码解说 ​

知识点介绍 ​

题目大意

解题思路

代码解说

知识点介绍