题解

题面描述

给定一个长度为 $n$ 的字符串 $s$，允许恰好进行一次交换操作：选定两个不同索引 $x\neq y$，将 $s_x$ 和 $s_y$ 互换。判断能否通过这一次交换使得最终字符串满足

若可以，输出 YES，否则输出 NO。

输入包含 $t$ 个测试用例，满足

• $1\le t\le 1000$,
• 每个字符串长度 $1\le n\le 10^5$,
• 所有测试用例中 $\sum n\le 10^5$。

思路

1. 目标串：将原串 $s$ 进行排序，记为目标串 $t$。
2. 统计差异：遍历下标 $0\le i<n$，统计 $s_i\ne t_i$ 的位置个数，记为 $cnt$。
3. 判断条件：
   • 若 $cnt=2$，则正好有两处字符错位，一次交换即可完成排序，输出 YES。
   • 若 $cnt=0$，表示原串已是非降序，但仍须恰好进行一次交换。此时只有当存在相同字符时，才可交换两相同字符而不破坏顺序，输出 YES；否则交换必破坏顺序，输出 NO。
   • 其它情况下（$cnt=1$ 或 $cnt>2$），一次交换无法完成排序，输出 NO。

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        // 将字符串 s 排序得到目标串 t
        string t = s;
        sort(t.begin(), t.end());
        // 统计 s 和 t 在对应位置上不同的次数
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (s[i] != t[i]) {
                cnt++;
            }
        }
        if (cnt == 2) {
            // 恰好两处不同，通过一次交换即可排序
            cout << "YES\n";
        } else if (cnt == 0) {
            // 已有序，但必须进行一次交换
            // 只有存在重复字符时，交换相同字符才不会破坏顺序
            vector<int> freq(26, 0);
            bool dup = false;
            for (char c : s) {
                if (++freq[c - 'a'] > 1) {
                    dup = true;
                    break;
                }
            }
            cout << (dup ? "YES\n" : "NO\n");
        } else {
            // 其它情况无法通过一次交换排序
            cout << "NO\n";
        }
    }
    return 0;
}

Python

import sys
from collections import Counter

def solve():
    # 读取测试用例数量
    t = int(sys.stdin.readline())
    for _ in range(t):
        # 读取字符串长度和内容
        n = int(sys.stdin.readline())
        s = sys.stdin.readline().strip()
        # 排序得到目标非降序字符串
        t_str = ''.join(sorted(s))
        # 记录不同位置的索引
        diff = [i for i in range(n) if s[i] != t_str[i]]
        cnt = len(diff)
        if cnt == 2:
            # 恰好两处不同，可交换排序
            print("YES")
        elif cnt == 0:
            # 已有序，但必须进行一次交换
            # 只有存在重复字符时，交换相同字符才无害
            if any(v > 1 for v in Counter(s).values()):
                print("YES")
            else:
                print("NO")
        else:
            # 其它情况无法完成
            print("NO")

if __name__ == '__main__':
    solve()

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 读取测试用例数量
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            // 读取字符串长度和内容
            int n = Integer.parseInt(br.readLine());
            String s = br.readLine();
            // 将字符串转换为字符数组并排序得到目标
            char[] a = s.toCharArray();
            char[] b = s.toCharArray();
            Arrays.sort(b);
            // 统计不同位置数
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                if (a[i] != b[i]) {
                    cnt++;
                }
            }
            if (cnt == 2) {
                // 恰好两处不同，可交换排序
                System.out.println("YES");
            } else if (cnt == 0) {
                // 已有序，但必须交换一次
                // 只有存在重复字符时才可交换相同字符不破坏顺序
                int[] freq = new int[26];
                boolean dup = false;
                for (char c : a) {
                    if (++freq[c - 'a'] > 1) {
                        dup = true;
                        break;
                    }
                }
                System.out.println(dup ? "YES" : "NO");
            } else {
                // 其它情况无法一次交换排序
                System.out.println("NO");
            }
        }
    }
}

题目内容

小美现在有一个字符串 $s$，她现在进行恰好一次操作。

• 交换两个索引的字母，即选定 $x, y (x ≠ y)$，交换 $s_x$ 和 $s_y$。

她想知道能不能使得 $s$ 满足 $s_0 \leq s_1 \leq s_2 \leq ··· \leq s_{n-1}$。

你能帮帮她吗?

输入描述

第一行一个整数 $t$，表示有 $t(1\leq t\leq 1000)$ 组数据。

每组数据第一行一个整数 $n(1\leq n\leq 100000)$，表示字符串的长度。

每组数据第二行一个字符串 $s$。

$s$ 仅包含小写字母且单个测试文件满足 $\sum n \leq 10^5$。

输出描述

对于每组数据，如果可以使得 $s$ 满足 $s_0 \leq s_1 \leq s_2 \leq ··· \leq s_{n-1}$，则输出 YES，否则输出 NO。

示例1

输入

2
3
acb
3
bca

输出

YES
NO