题目描述

给定两个字符串 str1 和 str2，如果字符串 str1 中的字符经过排列组合后，字符串 str2 中有一个字符串是 str1 的子串，则认为 str1 是 str2 的关联子串。

若 str1 是 str2 的关联子串，请返回子串在 str2 的起始位置；若不是关联子串，则返回 -1。

思路

要解决这个问题，我们可以利用滑动窗口和字符计数的技巧。具体步骤如下：

1. 字符计数：先统计 str1 中每个字符的出现次数。
2. 滑动窗口：然后我们在 str2 上使用一个大小为 len(str1) 的滑动窗口，同时维护一个窗口内字符的计数。
3. 比较计数：每次滑动窗口时，我们检查窗口中的字符计数是否与 str1 的字符计数相同，如果相同，则返回当前窗口的起始位置。
4. 边界处理：需要注意边界条件和窗口的更新。

代码分析

1. 时间复杂度：O(n + m)，其中 n 是 str1 的长度，m 是 str2 的长度。我们需要遍历 str2 进行窗口滑动，并在每一步中更新字符计数。
2. 空间复杂度：O(1)，因为字符集固定为小写字母，最多有 26 个字符。

cpp

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

using namespace std;

int findAnagramSubstring(string str1, string str2) {
    int len1 = str1.size();
    int len2 = str2.size();
    
    if (len1 > len2) return -1;

    // 统计str1中的字符频率
    unordered_map<char, int> charCount1, charCount2;
    for (char c : str1) {
        charCount1[c]++;
    }

    // 初始化窗口
    for (int i = 0; i < len1; i++) {
        charCount2[str2[i]]++;
    }

    // 检查第一个窗口
    if (charCount1 == charCount2) {
        return 0;
    }

    // 滑动窗口
    for (int i = len1; i < len2; i++) {
        charCount2[str2[i]]++;  // 加入新的字符
        charCount2[str2[i - len1]]--;  // 移除最左边的字符

        // 如果移除后的字符频率为0，则删除该字符
        if (charCount2[str2[i - len1]] == 0) {
            charCount2.erase(str2[i - len1]);
        }

        // 比较窗口字符计数
        if (charCount1 == charCount2) {
            return i - len1 + 1; // 返回起始位置
        }
    }

    return -1; // 没有找到
}

int main() {
    string str1, str2;
    cin >> str1 >> str2;
    int result = findAnagramSubstring(str1, str2);
    cout << result << endl;
    return 0;
}

python

def find_anagram_substring(str1, str2):
    len1 = len(str1)
    len2 = len(str2)

    if len1 > len2:
        return -1

    # 统计 str1 中的字符频率
    char_count1 = {}
    char_count2 = {}

    for c in str1:
        char_count1[c] = char_count1.get(c, 0) + 1

    # 初始化窗口
    for i in range(len1):
        char_count2[str2[i]] = char_count2.get(str2[i], 0) + 1

    # 检查第一个窗口
    if char_count1 == char_count2:
        return 0

    # 滑动窗口
    for i in range(len1, len2):
        # 加入新的字符
        char_count2[str2[i]] = char_count2.get(str2[i], 0) + 1
        # 移除最左边的字符
        left_char = str2[i - len1]
        char_count2[left_char] -= 1

        # 如果移除后的字符频率为0，则删除该字符
        if char_count2[left_char] == 0:
            del char_count2[left_char]

        # 比较窗口字符计数
        if char_count1 == char_count2:
            return i - len1 + 1  # 返回起始位置

    return -1  # 没有找到


# 主函数
if __name__ == "__main__":
    input_data = input().strip()
    str1, str2 = input_data.split()  # 分割输入
    result = find_anagram_substring(str1, str2)
    print(result)

java

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    public static int findAnagramSubstring(String str1, String str2) {
        int len1 = str1.length();
        int len2 = str2.length();
        
        if (len1 > len2) {
            return -1;
        }

        // 统计 str1 中的字符频率
        Map<Character, Integer> charCount1 = new HashMap<>();
        Map<Character, Integer> charCount2 = new HashMap<>();

        for (char c : str1.toCharArray()) {
            charCount1.put(c, charCount1.getOrDefault(c, 0) + 1);
        }

        // 初始化窗口
        for (int i = 0; i < len1; i++) {
            charCount2.put(str2.charAt(i), charCount2.getOrDefault(str2.charAt(i), 0) + 1);
        }

        // 检查第一个窗口
        if (charCount1.equals(charCount2)) {
            return 0;
        }

        // 滑动窗口
        for (int i = len1; i < len2; i++) {
            // 加入新的字符
            charCount2.put(str2.charAt(i), charCount2.getOrDefault(str2.charAt(i), 0) + 1);
            // 移除最左边的字符
            char leftChar = str2.charAt(i - len1);
            charCount2.put(leftChar, charCount2.get(leftChar) - 1);

            // 如果移除后的字符频率为0，则删除该字符
            if (charCount2.get(leftChar) == 0) {
                charCount2.remove(leftChar);
            }

            // 比较窗口字符计数
            if (charCount1.equals(charCount2)) {
                return i - len1 + 1;  // 返回起始位置
            }
        }

        return -1;  // 没有找到
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine().trim();
        String[] strings = input.split(" ");  // 分割输入
        String str1 = strings[0];
        String str2 = strings[1];
        int result = findAnagramSubstring(str1, str2);
        System.out.println(result);
        scanner.close();
    }
}

题目内容

给定两个字符串$str1$和$str2$，如果字符串$str1$中的字符，经过排列组合后的字符串中，只要有一个字符串是$str2$的子串，则认为$str1$是$str2$的关联子串。

若$str1$是$str2$的关联子串，请返回子串在$str2$的起始位置；

若不是关联子串，则返回$-1$。

输入描述

输入两个字符串，分别为题目中描述的$str1$、$str2$。

输出描述

若$str1$是$str2$的关联子串，请返回子串在$str2$的起始位置；

若不是关联子串，则返回$-1$。

若 $str2$ 中有多个 $str1$ 的组合子串，请返回最小的起始位置。

备注

• 输入的字符串只包含小写字母；
• 两个字符串的长度范围$[1, 100000]$之间；

样例1

输入

abc efghicbaiii

输出

5

说明

$str2$包含$str1$的一种排列组合（"$cab$")，此组合在$str2$的字符串起始位置为$5$（从$0$开始计数）

样例2

输入

abc efghiccaiii

输出

-1

说明

“$abc$”字符串中三个字母的各种组合（$abc、acb、bac、bca、cab、cba$），$str2$中均不包含，因此返回$-1$