字符串奇偶性问题

[题目链接](https://www.nowcoder.com/practice/49b1dfff37014c17bd726796ee5ef388)

题意

对于长度为 的字符串 ，定义 为：

• 的全部奇数位字符（位置 1, 3, 5, ...），按字典序从小到大排序；
• 拼接上 的全部偶数位字符（位置 2, 4, 6, ...），按字典序从大到小排序。

给定长度为 的字符串 ，取出其所有长度为 的子串，分别构造 值，统计有多少个不同的 值。

字典序按 ASCII 码，大写字母 (A=65) 小于小写字母 (a=97)。

思路

关键观察

的值仅取决于子串中奇数位字符的多重集和偶数位字符的多重集，与字符的原始顺序无关。因此，对每个长度为 的子串：

1. 分别提取奇数位（下标 0, 2, 4, ... 对应位置 1, 3, 5, ...）和偶数位（下标 1, 3, 5, ... 对应位置 2, 4, 6, ...）的字符；
2. 奇数位字符升序排序，偶数位字符降序排序；
3. 将两部分拼接得到 值，用 set 记录所有不同的 值。

算法

直接枚举所有 个子串，对每个子串计算 值并插入集合，最终输出集合大小。

时间复杂度：，对本题数据规模完全可行。

样例演示

第一组：n=5, k=4, S="bAbbb"

长度为 4 的子串：

• bAbb（下标 0~3）：奇数位 b,b（排序：bb），偶数位 A,b（降序：bA）→ = bb + bA = bbbA
• Abbb（下标 1~4）：奇数位 A,b（排序：Ab），偶数位 b,b（降序：bb）→ = Ab + bb = Abbb

两个 值不同，答案为 2。

第二组：n=6, k=3, S="nuhhhh"

长度为 3 的子串：nuh, uhh, hhh, hhh（最后两个相同）

• nuh：奇数位 n,h（排序：hn），偶数位 u（降序：u）→ hnu
• uhh：奇数位 u,h（排序：hu），偶数位 h（降序：h）→ huh
• hhh：奇数位 h,h（排序：hh），偶数位 h（降序：h）→ hhh
• hhh：同上 → hhh（重复）

共 3 个不同的 值，答案为 3。

代码

C++

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while (t--) {
        int n, k;
        cin >> n >> k;
        string s;
        cin >> s;

        set<string> distinct;

        for (int i = 0; i <= n - k; i++) {
            string odd_chars, even_chars;
            for (int j = 0; j < k; j++) {
                if ((j + 1) % 2 == 1) {
                    odd_chars += s[i + j];
                } else {
                    even_chars += s[i + j];
                }
            }
            sort(odd_chars.begin(), odd_chars.end());
            sort(even_chars.begin(), even_chars.end(), greater<char>());

            distinct.insert(odd_chars + even_chars);
        }

        cout << distinct.size() << "\n";
    }

    return 0;
}

Java

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

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().trim());
        StringBuilder sb = new StringBuilder();

        while (t-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            String s = br.readLine().trim();

            Set<String> distinct = new HashSet<>();

            for (int i = 0; i <= n - k; i++) {
                StringBuilder oddChars = new StringBuilder();
                StringBuilder evenChars = new StringBuilder();

                for (int j = 0; j < k; j++) {
                    if ((j + 1) % 2 == 1) {
                        oddChars.append(s.charAt(i + j));
                    } else {
                        evenChars.append(s.charAt(i + j));
                    }
                }

                char[] odd = oddChars.toString().toCharArray();
                char[] even = evenChars.toString().toCharArray();
                Arrays.sort(odd);
                Arrays.sort(even);
                for (int l = 0, r = even.length - 1; l < r; l++, r--) {
                    char tmp = even[l]; even[l] = even[r]; even[r] = tmp;
                }

                distinct.add(new String(odd) + new String(even));
            }

            sb.append(distinct.size()).append("\n");
        }

        System.out.print(sb);
    }
}