解题思路

我们要在字符串中出现子串 "abcdefghijklmnopqrstuvwxyz"（长度为 26，下文记为目标串 T），允许的操作是：选择一个下标把字符改成任意小写字母。问最少需要多少次操作；若无法做到输出 -1。

关键事实

• 若 n < 26，无论如何修改都不可能出现长度为 26 的子串，答案为 -1。
• 若 n ≥ 26，一定可以：选择任意长度为 26 的窗口，把其中的字符逐个改成 T 对应位置即可。因此答案等于 所有长度为 26 的窗口与 T 的最小“汉明距离”（不相等字符的个数）。

算法（滑动窗口 / 枚举窗口）

• 预先把目标串 T="abcdefghijklmnopqrstuvwxyz" 固定下来。
• 对每个起点 i = 0..n-26，计算窗口 s[i..i+25] 与 T 的不同字符数 diff(i)。
• 取 min diff(i) 即为最少操作次数。
• 由于 26 很小，可以直接对每个窗口做 26 次比较，整体仍是线性的；也可做滑动更新，这里为了简洁使用直接比较。

实现要点：

• 全程只做字符比较与计数，使用 64 位整型并不必要；普通整型即可。
• 输入为多组数据，保证 $\sum n \le 2\times 10^5$。

复杂度分析

• 每个窗口比较 26 次，共有 n-25 个窗口：时间复杂度 $O(26\cdot (n-25)) = O(n)$。
• 仅使用常数额外空间：空间复杂度 $O(1)$。

代码实现

Python

import sys

# 功能函数：返回最少修改次数；n<26 时返回 -1
def min_ops_to_full_alphabet(n, s):
    if n < 26:
        return -1
    T = "abcdefghijklmnopqrstuvwxyz"
    ans = 26  # 最大不超过 26
    # 枚举所有长度为 26 的窗口
    for i in range(n - 26 + 1):
        diff = 0
        # 逐位比较，统计不同字符个数
        for j in range(26):
            if s[i + j] != T[j]:
                diff += 1
        if diff < ans:
            ans = diff
            if ans == 0:  # 已经出现目标串，提前结束
                break
    return ans

def main():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    T = int(next(it))
    out = []
    for _ in range(T):
        n = int(next(it))
        s = next(it)
        out.append(str(min_ops_to_full_alphabet(n, s)))
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

Java

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

public class Main {

    // 功能函数：计算最少操作次数；n<26 时返回 -1
    static int minOpsToAlphabet(int n, String s) {
        if (n < 26) return -1;
        char[] arr = s.toCharArray();
        char[] T = "abcdefghijklmnopqrstuvwxyz".toCharArray();
        int ans = 26;
        // 枚举每个长度为 26 的窗口
        for (int i = 0; i + 26 <= n; i++) {
            int diff = 0;
            for (int j = 0; j < 26; j++) {
                if (arr[i + j] != T[j]) diff++;
            }
            if (diff < ans) {
                ans = diff;
                if (ans == 0) break; // 已经匹配，提前结束
            }
        }
        return ans;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder out = new StringBuilder();
        int T = Integer.parseInt(br.readLine().trim());
        for (int tc = 0; tc < T; tc++) {
            int n = Integer.parseInt(br.readLine().trim());
            String s = br.readLine().trim();
            out.append(minOpsToAlphabet(n, s)).append('\n');
        }
        System.out.print(out.toString());
    }
}

C++

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

// 功能函数：返回最少修改次数；n<26 时返回 -1
int min_ops_to_alphabet(int n, const string& s) {
    if (n < 26) return -1;
    const string T = "abcdefghijklmnopqrstuvwxyz";
    int ans = 26;
    // 枚举每个窗口，统计与 T 的不同字符数
    for (int i = 0; i + 26 <= n; ++i) {
        int diff = 0;
        for (int j = 0; j < 26; ++j) {
            if (s[i + j] != T[j]) ++diff;
        }
        ans = min(ans, diff);
        if (ans == 0) break; // 已匹配
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; 
    if (!(cin >> T)) return 0;
    while (T--) {
        int n; string s;
        cin >> n >> s;
        cout << min_ops_to_alphabet(n, s) << "\n";
    }
    return 0;
}

题目内容

给定一个长度为 $n$ 的字符串 $s$，字符串仅由小写字母组成，下标从 $1$ 开始。你可以对字符串执行以下操作任意次:

• 选择一个下标 $i$，将 $s_i$ 修改为任意小写字母;

请问最少需要多少次操作，才能让字符串中出现子串"$abcdefghijklmnopqrstuvwxyz$"。

【名词解释】

• 子串:子串为从原字符串中连续地选择一段字符(可以全选、可以不选)得到的新字符串。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≦T≦10^4)$，代表数据组数;

此后对于每组测试数据:

• 第一行输入一个整数 $n(1≦n≦2×10^5)$，表示字符串长度;

• 第二行输入一个长度为 $n$、仅由小写字母构成的字符串 $s$ .

除此之外，保证所有测试数据中几的总和不超过 $2×10^5$ 。

输出描述

对于每组测试数据，新起一行，输出一个整数，代表最少的操作次数;

• 如果不存在使字符串中出现完整英文字母序列的方案，则输出 $-1$ .

样例1

输入

3
37
abcdefghijklmnopqrstuvwxyzzzzzzzzzzzz
26
bcdefghijkimnopqrstuvwxyza
25
abcdefghijklmnopqrstuvwxy

输出

0
26
-1