题解

题目解释

给定两个字符串 s1 和 s2，以及一个正整数 k。要求在字符串 s2 中找到一个长度为 len(s1) + k 的子串，使得：

1. 该子串包含 s1 中的所有字母；
2. 每个字母在子串中的出现次数不少于其在 s1 中的出现次数。

需要找出满足上述条件的最左侧的子串的起始下标，如果不存在这样的子串，则输出 -1。

思路分析

题目的本质是在字符串 s2 中找到长度为 len(s1) + k 的最左侧子串，该子串的字母频次数满足 s1 的要求。

考虑以下几点：

1. 窗口长度固定：由于子串长度固定为 len(s1) + k，可以使用滑动窗口的方法遍历 s2 中所有可能的子串。

2. 字母频次要求：需要检查每个窗口内的字母频次是否满足 s1 的要求。

为此，我们可以：

• 预处理 s1 中每个字母的需要次数，存储在数组 need 中。
• 维护一个滑动窗口，窗口大小为 len(s1) + k，窗口内的字母频次存储在数组 counts 中。

在滑动窗口移动的过程中，我们需要高效地判断当前窗口是否满足条件。为此，使用一个变量 deficit 来表示当前窗口中缺失的字母种类数。

具体步骤

1. 初始化：

   • 计算 s1 中每个字母的需要次数，存储在 need 数组中。
   • 初始化滑动窗口，窗口大小为 len(s1) + k，计算窗口内的字母频次，存储在 counts 数组中。
   • 初始化 deficit，统计在当前窗口中，哪些字母的出现次数少于 need 中的要求。

2. 滑动窗口遍历：

   • 检查当前窗口：如果 deficit == 0，说明当前窗口满足条件，输出起始下标。
   • 移动窗口：
     • 移除左端字符，更新 counts 和 deficit：
       • 如果移除的字符在 need 中有要求，且移除前字符的出现次数等于要求次数，那么移除后，该字符的出现次数将少于要求次数，因此 deficit 加 1。
       • 无论如何，都要减少该字符在 counts 中的计数。
     • 添加右端字符，更新 counts 和 deficit：
       • 增加该字符在 counts 中的计数。
       • 如果添加的字符在 need 中有要求，且添加后字符的出现次数等于要求次数，那么 deficit 减 1。

3. 结束条件：如果遍历完所有可能的窗口仍未找到满足条件的子串，输出 -1。

时间复杂度分析

• 预处理阶段：

  • 计算 s1 中的 need 数组，时间复杂度为 O(len(s1))。

• 滑动窗口遍历：

  • 窗口大小固定为 len(s1) + k，滑动次数为 len(s2) - windowSize + 1，即 O(len(s2))。

• 窗口内操作：

  • 每次滑动窗口时，更新 counts 和 deficit，这些操作都是 O(1) 的。

• 总时间复杂度：O(len(s1) + len(s2))，由于 len(s1) 可能接近 1,000,000，len(s2) 可能接近 20,000,000，因此需要使用高效的线性算法。

c++

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    string s1, s2;
    int k;

    // 输入
    cin >> s1 >> s2 >> k;

    int n1 = s1.length();
    int n2 = s2.length();

    // 如果需要的子串长度超过s2的长度，直接输出-1
    if (n1 + k > n2) {
        cout << -1 << endl;
        return 0;
    }

    vector<int> need(26, 0);   // s1中需要的字符计数
    vector<int> counts(26, 0); // 当前窗口的字符计数

    // 统计s1中每个字符的需要次数
    for (char c : s1) {
        need[c - 'a']++;
    }

    int windowSize = n1 + k;

    // 初始化窗口内字符计数
    for (int i = 0; i < windowSize; i++) {
        counts[s2[i] - 'a']++;
    }

    // 初始化缺失字符计数
    int deficit = 0;
    for (int i = 0; i < 26; i++) {
        if (counts[i] < need[i]) {
            deficit++;
        }
    }

    // 滑动窗口
    for (int i = 0; i <= n2 - windowSize; i++) {
        // 如果没有缺失的字符，输出起始下标
        if (deficit == 0) {
            cout << i << endl;
            return 0;
        }

        // 移动窗口，更新字符计数和缺失计数
        if (i + windowSize < n2) {
            int leftChar = s2[i] - 'a';
            int rightChar = s2[i + windowSize] - 'a';

            // 移除左边字符
            if (counts[leftChar] == need[leftChar]) {
                deficit++;
            }
            counts[leftChar]--;

            // 添加右边字符
            counts[rightChar]++;
            if (counts[rightChar] == need[rightChar]) {
                deficit--;
            }
        } else {
            // 已经到达最后一个窗口，无需再移动
            break;
        }
    }

    // 如果没有找到符合条件的子串，输出-1
    cout << -1 << endl;
    return 0;
}

python

def find_substring(s1, s2, k):
    n1 = len(s1)
    n2 = len(s2)

    # 如果需要的子串长度超过s2的长度，直接输出-1
    if n1 + k > n2:
        return -1

    need = [0] * 26  # s1中需要的字符计数
    counts = [0] * 26  # 当前窗口的字符计数

    # 统计s1中每个字符的需要次数
    for c in s1:
        need[ord(c) - ord('a')] += 1

    window_size = n1 + k

    # 初始化窗口内字符计数
    for i in range(window_size):
        counts[ord(s2[i]) - ord('a')] += 1

    # 初始化缺失字符计数
    deficit = sum(1 for i in range(26) if counts[i] < need[i])

    # 滑动窗口
    for i in range(n2 - window_size + 1):
        # 如果没有缺失的字符，输出起始下标
        if deficit == 0:
            return i

        # 移动窗口，更新字符计数和缺失计数
        if i + window_size < n2:
            left_char = ord(s2[i]) - ord('a')
            right_char = ord(s2[i + window_size]) - ord('a')

            # 移除左边字符
            if counts[left_char] == need[left_char]:
                deficit += 1
            counts[left_char] -= 1

            # 添加右边字符
            counts[right_char] += 1
            if counts[right_char] == need[right_char]:
                deficit -= 1

    # 如果没有找到符合条件的子串，输出-1
    return -1


# 输入
s1 = input().strip()
s2 = input().strip()
k = int(input().strip())

# 输出结果
result = find_substring(s1, s2, k)
print(result)

java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        String s1 = scanner.next();
        String s2 = scanner.next();
        int k = scanner.nextInt();
        
        int n1 = s1.length();
        int n2 = s2.length();

        // 如果需要的子串长度超过s2的长度，直接输出-1
        if (n1 + k > n2) {
            System.out.println(-1);
            return;
        }

        int[] need = new int[26];   // s1中需要的字符计数
        int[] counts = new int[26]; // 当前窗口的字符计数

        // 统计s1中每个字符的需要次数
        for (char c : s1.toCharArray()) {
            need[c - 'a']++;
        }

        int windowSize = n1 + k;

        // 初始化窗口内字符计数
        for (int i = 0; i < windowSize; i++) {
            counts[s2.charAt(i) - 'a']++;
        }

        // 初始化缺失字符计数
        int deficit = 0;
        for (int i = 0; i < 26; i++) {
            if (counts[i] < need[i]) {
                deficit++;
            }
        }

        // 滑动窗口
        for (int i = 0; i <= n2 - windowSize; i++) {
            // 如果没有缺失的字符，输出起始下标
            if (deficit == 0) {
                System.out.println(i);
                return;
            }

            // 移动窗口，更新字符计数和缺失计数
            if (i + windowSize < n2) {
                int leftChar = s2.charAt(i) - 'a';
                int rightChar = s2.charAt(i + windowSize) - 'a';

                // 移除左边字符
                if (counts[leftChar] == need[leftChar]) {
                    deficit++;
                }
                counts[leftChar]--;

                // 添加右边字符
                counts[rightChar]++;
                if (counts[rightChar] == need[rightChar]) {
                    deficit--;
                }
            } else {
                // 已经到达最后一个窗口，无需再移动
                break;
            }
        }

        // 如果没有找到符合条件的子串，输出-1
        System.out.println(-1);
    }
}

题目内容

给定两个字符串 $s_1$ 和 $s_2$ 和正整数 $k$，其中 $s_1$ 长度为 $n_1$，$s_2$ 长度为 $n_2$。

在 $s_2$ 中选一个子串，若满足下面条件，则称 $s_2$ 以长度 $k$ 冗余覆盖 $s_1$

• 该子串长度为 $n_1 + k$
• 该子串中包含 $s_1$ 中全部字母
• 该子串每个字母出现次数不小于 $s_1$ 中对应的字母

给定 $s_1，s_2，k$，求最左侧的 $s_2$ 以长度 $k$ 冗余覆盖 $s_1$ 的子串的首个元素的下标，如果没有返回$-1$。

举例：

$s_1$ = "$ab$"

$s_2$ = "$aabcd$"

$k = 1$

则子串 “$aab$” 和 "$abc$" 均满足此条件，由于 "$aab$" 在 "$abc$" 的左侧，"$aab$" 的第一个元素下标为 $0$，因此输出 $0$

输入描述

输入三行，第一行为 $s_1$，第二行为 $s_2$，第三行为 $k$

• $s_1$ 和 $s_2$ 只包含小写字母

输出描述

最左侧的 $s_2$ 以长度 $k$ 冗余覆盖 $s_1$ 的子串首个元素下标，如果没有返回 $-1$。

备注

• $0 ≤ len(s_1) ≤ 1000000$
• $0 ≤ len(s_2) ≤ 20000000$
• $0 ≤ k ≤ 1000$

样例1

输入

ab
aabcd
1

输出

0

说明

子串$aab$和$abc$符合要求，由于$aab$在$abc$的左侧，因此输出$aab$的下标：$0$

样例2

输入

abc
dfs
10

输出

-1

说明

$s_2$无法覆盖$s_1$，输出 $-1$