喵呜~ 各位铲屎官，今天本猫娘要给大家带来一道有趣的题目哦！这道题叫做 "E. Alternating String"，是关于字符串操作和优化的，听起来是不是很有趣呀？本猫娘已经迫不及待要和大家分享我的解题思路啦！

题目大意：什么是“交错字符串”？

首先，我们来理解一下题目的核心概念——“交错字符串”（Alternating String）。题目里说，一个由小写拉丁字母组成的字符串 s，如果满足以下三个条件，它就是“交错字符串”：

1. 偶数位置的字符都相同。 (注意：这里的偶数位置指的是1-based indexing，也就是第2、4、6...个字符)
2. 奇数位置的字符都相同。 (同样是1-based indexing，也就是第1、3、5...个字符)
3. 字符串的长度是偶数。

举个例子喵：'abab' 和 'gg' 都是交错字符串，因为 'abab' 的奇数位都是 'a'，偶数位都是 'b'，长度是4（偶数）；'gg' 的奇数位都是 'g'，偶数位也是 'g'（虽然只有一位，但规则仍然成立），长度是2（偶数）。

而 'aba' 就不是，因为长度是奇数；'ggwp' 也不是，因为虽然长度是偶数，但偶数位置的字符不都相同 ('g' 和 'w')。

现在，问题来了！我们手头有一个字符串，但是它可能不是交错字符串。我们有两种操作可以把它变成交错字符串，而且要用最少的操作次数喵：

• 删除操作： 选择一个位置 i，删除第 i 个字符。这个操作最多只能执行 1 次。
• 替换操作： 选择一个位置 i，将 s[i] 替换成任意其他字母。这个操作可以执行任意次。

我们需要找出将给定字符串变成交错字符串所需的最小操作次数。

题目分析与解题思路

这道题的难点在于“最多只能删除一次”这个限制。这意味着我们需要考虑两种情况：

1. 不进行删除操作。
2. 进行一次删除操作。

然后在这两种情况中，分别计算所需的最小替换次数，最后取最小值。

情况一：不进行删除操作

如果选择不删除任何字符，那么原始字符串的长度 n 必须是偶数，才能满足“交错字符串”的第三个条件。如果 n 本身就是奇数，那么不删除操作就永远无法得到交错字符串，这种情况下我们直接忽略这种方案（或者说，这种方案的代价是无限大）。

如果 n 是偶数，那么我们只需要通过替换操作来使奇数位置的字符都相同，偶数位置的字符也都相同。为了最小化替换次数，我们应该让奇数位置的字符都变成出现次数最多的那个字符，偶数位置的字符也变成出现次数最多的那个字符。

具体来说，我们可以遍历字符串，统计所有奇数位置上每个字符的出现次数，找到出现次数最多的那个字符，假设它的出现次数是 max_odd_freq。那么，奇数位置上需要替换的字符数量就是 n/2 - max_odd_freq。同理，统计所有偶数位置上每个字符的出现次数，找到出现次数最多的那个字符，假设它的出现次数是 max_even_freq。那么，偶数位置上需要替换的字符数量就是 n/2 - max_even_freq。

总的替换次数就是 (n/2 - max_odd_freq) + (n/2 - max_even_freq) = n - (max_odd_freq + max_even_freq)。

注意： 题目中的奇数/偶数位置是1-based indexing。在C++中字符串是0-indexed。

• 1-based odd positions (1, 3, 5, ...) 对应 0-indexed even positions (0, 2, 4, ...)。
• 1-based even positions (2, 4, 6, ...) 对应 0-indexed odd positions (1, 3, 5, ...)。 所以，我们需要统计 0-indexed 偶数位置的字符频率和 0-indexed 奇数位置的字符频率。

情况二：进行一次删除操作

如果选择删除一个字符，那么原始字符串的长度 n 可以是奇数也可以是偶数。无论 n 是多少，删除一个字符后，字符串的长度 n-1 一定是偶数，这就满足了交错字符串的长度要求。

删除操作本身会花费 1 次操作。所以总的代价是 1 + 替换次数。我们的目标是最小化 替换次数。

删除一个字符 s[i] 后，字符串会变成 s[0...i-1] + s[i+1...n-1]。这里有一个很重要的细节：删除 s[i] 之后，所有原来在 s[i] 之后的字符 s[j] (其中 j > i) 的索引会变成 j-1。这意味着它们的奇偶性会发生变化！

例如，原始字符串 abcdefg (长度7)。 如果删除 c (索引2)： a (0) -> a (0) b (1) -> b (1) d (3) -> d (2) e (4) -> e (3) f (5) -> f (4) g (6) -> g (5) 可以看到，d 原来是奇数位置 (1-based 4)，现在变成了偶数位置 (1-based 3)。它的0-indexed从3变成了2。 总结一下：

• 对于被删除字符 s[i] 前的字符 s[j] ( j < i )，它们的索引和奇偶性不变。
• 对于被删除字符 s[i] 后的字符 s[j] ( j > i )，它们的索引变为 j-1，因此它们的奇偶性会翻转。
  • 如果 j 是 0-indexed 偶数， j-1 是 0-indexed 奇数。
  • 如果 j 是 0-indexed 奇数， j-1 是 0-indexed 偶数。

为了高效计算，我们可以预处理出前缀和。 我们用 pos_odd_pref[k][c] 表示在字符串 s[0...k-1] 中，字符 c 在 0-indexed 偶数位置（即1-based奇数位置）出现的次数。 用 pos_even_pref[k][c] 表示在字符串 s[0...k-1] 中，字符 c 在 0-indexed 奇数位置（即1-based偶数位置）出现的次数。

预处理： pos_odd_pref[k][c] 和 pos_even_pref[k][c] 可以通过遍历字符串一次来计算。 pos_odd_pref[k] = pos_odd_pref[k-1]pos_even_pref[k] = pos_even_pref[k-1] 如果 (k-1) 是 0-indexed 偶数，则 pos_odd_pref[k][s[k-1]-'a']++。 如果 (k-1) 是 0-indexed 奇数，则 pos_even_pref[k][s[k-1]-'a']++。

有了前缀和，当我们考虑删除 s[i] 时，新的字符串的字符计数可以这样计算：

• 新的 0-indexed 偶数位置 (1-based 奇数位置) 的字符统计：

  • 来自 s[0...i-1] 中 0-indexed 偶数位置的字符：pos_odd_pref[i][c]
  • 来自 s[i+1...n-1] 中 0-indexed 奇数位置的字符（因为它们索引前移一位，奇偶性翻转了）：pos_even_pref[n][c] - pos_even_pref[i+1][c]
  • 总计：pos_odd_pref[i][c] + (pos_even_pref[n][c] - pos_even_pref[i+1][c])

• 新的 0-indexed 奇数位置 (1-based 偶数位置) 的字符统计：

  • 来自 s[0...i-1] 中 0-indexed 奇数位置的字符：pos_even_pref[i][c]
  • 来自 s[i+1...n-1] 中 0-indexed 偶数位置的字符（因为它们索引前移一位，奇偶性翻转了）：pos_odd_pref[n][c] - pos_odd_pref[i+1][c]
  • 总计：pos_even_pref[i][c] + (pos_odd_pref[n][c] - pos_odd_pref[i+1][c])

对于每个可能的删除位置 i (从 0 到 n-1)，我们计算出删除后字符串中新的 0-indexed 偶数位置字符的最大频率 max_new_odd_saved 和新的 0-indexed 奇数位置字符的最大频率 max_new_even_saved。 通过删除操作能保留下来的最多字符数量是 max_new_odd_saved + max_new_even_saved。 删除后字符串的长度是 n-1。所以替换次数是 (n-1) - (max_new_odd_saved + max_new_even_saved)。 总操作次数是 1 + (n-1) - (max_new_odd_saved + max_new_even_saved) = n - (max_new_odd_saved + max_new_even_saved)。 我们遍历所有可能的删除位置 i，找到使得 max_new_odd_saved + max_new_even_saved 最大的那个 i，从而得到最小的操作次数。

完整解题步骤

1. 读入 n 和字符串 s。

2. 处理 n 为偶数的情况 (不删除任何字符)：

   • 如果 n 是偶数，计算出不删除操作所需的最小替换次数 cost_no_del。
   • cost_no_del = n - (max_odd_freq_in_original_string + max_even_freq_in_original_string)。
   • 如果 n 是奇数，则 cost_no_del 视为无穷大。

3. 处理 n 为奇数的情况 (必须删除一个字符)：

   • 如果 n 是奇数，那么删除一个字符后，长度 n-1 必然是偶数，满足条件。
   • 计算出删除一个字符后所需的最小操作次数 cost_one_del。
   • 预处理 pos_odd_pref 和 pos_even_pref 数组。
   • 初始化 max_saved_chars = 0。
   • 遍历 i 从 0 到 n-1 (表示删除 s[i])：
     • 计算删除 s[i] 后，新的 0-indexed 偶数位置和 0-indexed 奇数位置上，每种字符的出现次数。
     • 找到新的 0-indexed 偶数位置上出现次数最多的字符的频率 current_max_new_odd_saved。
     • 找到新的 0-indexed 奇数位置上出现次数最多的字符的频率 current_max_new_even_saved。
     • 更新 max_saved_chars = max(max_saved_chars, current_max_new_odd_saved + current_max_new_even_saved)。
   • cost_one_del = n - max_saved_chars。

4. 最终答案：

   • 如果原始 n 是偶数，答案是 min(cost_no_del, cost_one_del)。
   • 如果原始 n 是奇数，答案是 cost_one_del (因为 cost_no_del 是无穷大)。
   • 喵呜~ 实际上，我们可以统一处理，因为如果 n 是奇数，cost_no_del 会很大， min 函数自然会选 cost_one_del。
   • 所以，如果原始 n 是偶数，我们计算两种情况的代价，取最小值。
   • 如果原始 n 是奇数，我们只能删除一个，所以只需要计算删除后的代价。

喵呜~ 代码实现来啦！

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>

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

    // 情况一：不进行删除操作 (原始字符串长度必须是偶数)
    if (n % 2 == 0) {
        // 统计 0-indexed 偶数位置 (对应 1-based 奇数位置) 的字符频率
        std::vector<int> odd_pos_counts(26, 0); 
        // 统计 0-indexed 奇数位置 (对应 1-based 偶数位置) 的字符频率
        std::vector<int> even_pos_counts(26, 0); 

        for (int i = 0; i < n; ++i) {
            if (i % 2 == 0) { // 0-indexed 偶数位置
                odd_pos_counts[s[i] - 'a']++;
            } else { // 0-indexed 奇数位置
                even_pos_counts[s[i] - 'a']++;
            }
        }

        // 找出奇数位置上出现频率最高的字符的次数
        int max_odd_freq = 0;
        if (n > 0) { // 防止 n=0 的极端情况，虽然题目n>=1
            max_odd_freq = *std::max_element(odd_pos_counts.begin(), odd_pos_counts.end());
        }
        
        // 找出偶数位置上出现频率最高的字符的次数
        int max_even_freq = 0;
        if (n > 0) {
            max_even_freq = *std::max_element(even_pos_counts.begin(), even_pos_counts.end());
        }
        
        // 计算不删除操作时的最小替换次数
        // 总长度 n，奇数位有 n/2 个，偶数位有 n/2 个
        // 需要替换的字符数 = (n/2 - max_odd_freq) + (n/2 - max_even_freq)
        // = n - (max_odd_freq + max_even_freq)
        std::cout << n - (max_odd_freq + max_even_freq) << "\n";
    } 
    // 情况二：进行一次删除操作 (原始字符串长度可以是奇数也可以是偶数)
    else {
        // 删除一个字符后，新的长度 n-1 必然是偶数，所以这种情况下一定需要删除一次。
        // 总操作数 = 1 (删除) + 替换次数
        // 替换次数 = (n-1) - max_saved_chars_after_deletion
        // 所以总操作数 = 1 + (n-1) - max_saved_chars_after_deletion = n - max_saved_chars_after_deletion

        // 预处理前缀和，方便计算删除某个字符后的频率
        // pos_odd_pref[k][c] 存储 s[0...k-1] 中，字符 c 在 0-indexed 偶数位置的出现次数
        std::vector<std::vector<int>> pos_odd_pref(n + 1, std::vector<int>(26, 0));
        // pos_even_pref[k][c] 存储 s[0...k-1] 中，字符 c 在 0-indexed 奇数位置的出现次数
        std::vector<std::vector<int>> pos_even_pref(n + 1, std::vector<int>(26, 0));

        for (int k = 1; k <= n; ++k) {
            pos_odd_pref[k] = pos_odd_pref[k - 1]; // 继承前一个状态
            pos_even_pref[k] = pos_even_pref[k - 1]; // 继承前一个状态
            
            // 根据当前字符 s[k-1] 的 0-indexed 位置 k-1 的奇偶性更新计数
            if ((k - 1) % 2 == 0) { // 0-indexed 偶数位置
                pos_odd_pref[k][s[k - 1] - 'a']++;
            } else { // 0-indexed 奇数位置
                pos_even_pref[k][s[k - 1] - 'a']++;
            }
        }

        int max_saved_chars = 0; // 记录删除某个字符后，能保留下来的字符的最大数量

        // 遍历每个可能的删除位置 i (0-indexed)
        for (int i = 0; i < n; ++i) {
            // 删除 s[i] 后，字符串被分成两部分：s[0...i-1] 和 s[i+1...n-1]
            // s[0...i-1] 部分的字符奇偶性不变
            // s[i+1...n-1] 部分的字符索引前移一位，奇偶性翻转

            int current_max_new_odd_saved = 0; // 删除 s[i] 后，新的 0-indexed 偶数位置上能保留的最大字符数
            int current_max_new_even_saved = 0; // 删除 s[i] 后，新的 0-indexed 奇数位置上能保留的最大字符数

            for (int c = 0; c < 26; ++c) { // 遍历所有可能的字符 'a' 到 'z'
                // 统计字符 c 在新的 0-indexed 偶数位置上的总数
                // = s[0...i-1] 中 0-indexed 偶数位置的 c 数量 
                // + s[i+1...n-1] 中 0-indexed 奇数位置的 c 数量 (因为索引前移一位，奇偶性翻转了)
                int new_odd_c_count = pos_odd_pref[i][c] + (pos_even_pref[n][c] - pos_even_pref[i + 1][c]);
                current_max_new_odd_saved = std::max(current_max_new_odd_saved, new_odd_c_count);

                // 统计字符 c 在新的 0-indexed 奇数位置上的总数
                // = s[0...i-1] 中 0-indexed 奇数位置的 c 数量 
                // + s[i+1...n-1] 中 0-indexed 偶数位置的 c 数量 (因为索引前移一位，奇偶性翻转了)
                int new_even_c_count = pos_even_pref[i][c] + (pos_odd_pref[n][c] - pos_odd_pref[i + 1][c]);
                current_max_new_even_saved = std::max(current_max_new_even_saved, new_even_c_count);
            }
            // 更新能保留下来的最大字符总数
            max_saved_chars = std::max(max_saved_chars, current_max_new_odd_saved + current_max_new_even_saved);
        }
        
        // 最终操作次数 = 1 (删除) + (n-1 - max_saved_chars) (替换) = n - max_saved_chars
        std::cout << n - max_saved_chars << "\n";
    }
}

int main() {
    // 优化输入输出，让程序跑得更快喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t; // 读入测试用例数量
    while (t--) {
        solve(); // 对每个测试用例调用 solve 函数
    }
    return 0;
}

知识点介绍：喵呜~

1. 字符串处理： 这道题就是典型的字符串处理问题，需要对字符串的字符进行遍历、统计和操作。
2. 前缀和（Prefix Sum）： 在处理删除操作时，为了高效地计算删除某个字符后子串的字符频率，我们使用了前缀和的思想。通过预先计算好每个前缀中不同字符在不同奇偶位置的出现次数，我们可以在 O(1) 的时间复杂度内得到任意子串的统计信息，从而将总的时间复杂度从 O(N^2 * 26) 降低到 O(N * 26)。这在 N 较大的时候非常有用喵！
   • pos_odd_pref[k][c] 表示 s[0...k-1] 中，字符 c 在 0-indexed 偶数位置的计数。
   • pos_even_pref[k][c] 表示 s[0...k-1] 中，字符 c 在 0-indexed 奇数位置的计数。
   • 那么，s[L...R] 中，字符 c 在 0-indexed 偶数位置的计数就是 pos_odd_pref[R+1][c] - pos_odd_pref[L][c]。
   • 在我们的代码里，pos_even_pref[n][c] - pos_even_pref[i+1][c] 就是 s[i+1...n-1] 这段后缀中，字符 c 在 0-indexed 奇数位置的计数。
3. 贪心策略： 为了最小化替换次数，我们总是让奇数位置的字符都变成奇数位置上出现次数最多的那个字符，偶数位置的字符都变成偶数位置上出现次数最多的那个字符。这就是一种贪心策略，因为它在每一步都做出了局部最优的选择，最终也导向了全局最优。
4. 分类讨论： 根据“最多只能删除一次”的限制，我们将问题分成了两种情况：不删除和删除一次。这种分类讨论是解决带有限制条件的优化问题的常用方法。
5. 时间复杂度分析：
   • 预处理前缀和：O(N * 26) = O(N)
   • 不删除操作：O(N) 遍历一次统计频率，O(26) 找最大频率。总计 O(N)。
   • 删除操作：外层循环 N 次 (遍历删除位置)，内层循环 26 次 (遍历字符 'a'~'z')。总计 O(N * 26) = O(N)。
   • 所以总的时间复杂度是 O(N)，对于 N = 2 * 10^5 是非常高效的喵！
6. 空间复杂度分析：
   • pos_odd_pref 和 pos_even_pref 数组的大小是 (N+1) * 26。所以空间复杂度是 O(N * 26) = O(N)。这在 N = 2 * 10^5 的情况下也是可以接受的。

喵呜~ 今天的题目讲解就到这里啦！希望大家都能理解这道题的精髓，掌握这些实用的算法技巧。下次再见咯！