Palindrome Shuffle

题目描述

题目链接

给定一个由小写拉丁字母组成的字符串s，你可以选择字符串的一个连续子串（可能是空的）并随意重排它。你的任务是确定为了将给定的字符串转换成回文，上述操作必须执行的最小子串长度。

输入

• 第一行包含一个整数t (1 ≤ t ≤ 10^4)，表示测试用例的数量。
• 每个测试用例的唯一一行包含一个字符串s (2 ≤ |s| ≤ 2⋅10^5)，由小写拉丁字母组成。
• 字符串s的长度为偶数，并且总是可以被转换为回文。

输出

对于每个测试用例，输出一个整数——为了将给定的字符串s转换为回文，需要重排的最小子串长度。

题解

双指针检查，l!=r时就进行调整处理。
处理部分：统计字符频率尝试从一端缩小需要调整的范围，直到找到一个满足条件的最短子串长度。另一端同理，比较两次结果取最小值。

完整代码

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define akitama return 0
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define fast_io cin.tie(nullptr)->ios::sync_with_stdio(false)
#define endl '\n'

/*
    AKITAMA CODEFORCES EDU174 D SOLUTION 25.2.18
    After Competition Time
    TARGET: up to C++23
*/

int check(string& s) {
    int len = s.size();
    vi cnt(26, 0), _cnt(26, 0);
    for (char c : s) cnt[c - 'a']++;
    int ans = len;
    for (int i = len - 1; i >= 0; -- i) {
        cnt[s[i] - 'a']--;
        _cnt[s[i] - 'a']++;
        if (i < len >> 1) {
            if (s[i] == s[len-i-1]) {
                _cnt[s[i] - 'a'] -= 2;
            } else {
                ans = min(ans, i+1);
                break;
            }
        }
        if (cnt[s[i] - 'a'] < _cnt[s[i] - 'a']) {
            ans = min(ans, i + 1);
            break;
        }
    }
    return ans;
}

void solve() {

    string s;
    cin >> s;
    int len = s.size();
    int l = 0, r = len - 1;
    while (l < r && s[l] == s[r]) {
        l++, r--;
    }
    if (l >= r) {
        cout << 0 << endl;
        return;
    }

    s = s.substr(l, r-l+1);
    //len = s.size();
    int ans = check(s);
    reverse(s.begin(), s.end());
    ans = min(ans, check(s));
    cout << ans << endl;

}

signed main(){
    fast_io;
    int _ ;
    cin >> _;
    while (_--) {
        solve();
    }
    akitama;
}