给定两个字符串str1和str2，如果字符串str1中的字符，经过排列组合后的字符串中，只要有一个字符串是str2的子串，则认为str1是str2的关联子串。
若str1是str2的关联子串，请返回子串在str2的起始位置；
若不是关联子串，则返回-1
若不是关联子串，则返回-1。
若str2中有多个str1的组合子串，请返回最小的起始位置
abc efghicbaiii
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">5
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">abc efghiccaiii
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">-1
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">这个问题可以通过 滑动窗口 的方式高效解决。具体步骤如下：
长度检查：首先，如果 str1 的长度大于 str2 的长度，直接返回 -1，因为不可能有子串满足条件。
字符计数：使用两个计数数组 count1 和 count2 来分别记录 str1 和 str2 的字符频率。每个字符的频率存在一个长度为 26 的数组中（假设只包含小写字母）。对于 str1，我们记录其每个字符的频率；然后，我们用滑动窗口的方式遍历 str2，并在窗口中计算字符的频率。
滑动窗口：我们从 str2 的前 n 个字符（n 是 str1 的长度）开始，检查其字符频率是否与 str1 的字符频率相同。如果相同，则返回当前窗口的起始位置。然后，我们滑动窗口：每次窗口右移一个字符，更新窗口的字符频率，移除窗口最左边的字符并添加新的字符，继续比较两者的频率是否相同。如果相同，则返回窗口的起始位置。
结束条件：如果遍历完所有可能的窗口后都没有找到符合的子串，则返回 -1
str1, str2 = input().split() # 输入两个字符串
# 定义一个函数来处理逻辑
def getResult():
n, m = len(str1), len(str2) # 获取两个字符串的长度
if n > m: # 如果 str1 长度大于 str2 长度，直接返回 -1
return -1
# 用于记录 str1 和 str2 中每个字符出现次数的数组
count1 = [0] * 26 # 记录 str1 中每个字符的频率
count2 = [0] * 26 # 记录 str2 中当前窗口中字符的频率
# 计算 str1 中每个字符的频率
for c in str1:
count1[ord(c) - ord('a')] += 1 # 将字符 c 转换为对应的索引并增加计数
# 初始化 str2 中的窗口，长度为 n
for i in range(n):
count2[ord(str2[i]) - ord('a')] += 1 # 统计窗口中字符的频率
# 如果 str1 和 str2 的前 n 个字符频率一致，直接返回 0，表示从第 0 位开始
if count1 == count2:
return 0
# 滑动窗口，从第 n 位开始，逐个字符滑动窗口
for i in range(n, m):
# 增加当前字符的计数
count2[ord(str2[i]) - ord('a')] += 1
# 移除窗口最左边的字符
count2[ord(str2[i - n]) - ord('a')] -= 1
# 如果此时的窗口字符频率与 str1 的频率一致，返回当前窗口的起始位置
if count1 == count2:
return i - n + 1
# 如果遍历完所有窗口都没有找到匹配的子串，返回 -1
return -1
# 调用函数并输出结果
print(getResult())
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">为了解决这个问题，我们可以使用 滑动窗口 和 字符计数 的方法。具体步骤如下：
初始化字符计数：首先计算 str1 中每个字符的频率，存储在 targetCount 数组中。然后，使用一个滑动窗口遍历 str2，在窗口中计算字符的频率，存储在 windowCount 数组中。
初始窗口匹配：首先，检查 str2 的前 n 个字符（n 是 str1 的长度）是否与 str1 的字符频率匹配。如果匹配，返回起始索引 0。
滑动窗口：将窗口从 str2 的前 n 个字符滑动到后面的字符。每次滑动窗口时，更新 windowCount，即移除窗口最左边的字符并加入窗口右边的新字符。每次更新后，检查窗口中的字符频率是否与 targetCount 匹配，如果匹配，返回当前窗口的起始位置。
结束条件：如果遍历完所有窗口仍未找到匹配的子串，返回 -1。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String str1 = scanner.next(); // 读取第一个字符串
String str2 = scanner.next(); // 读取第二个字符串
System.out.println(findSubstr(str1, str2)); // 输出结果
}
// findSubstr 方法用于找到第一个符合条件的子串
public static int findSubstr(String str1, String str2) {
// 创建两个数组，分别记录 str1 和滑动窗口中字符的出现次数
int[] targetCount = new int[26]; // str1 的字符频率数组
int[] windowCount = new int[26]; // str2 中当前窗口的字符频率数组
// 统计 str1 中每个字符的频率
for (char c : str1.toCharArray()) {
targetCount[c - 'a']++; // 将字符转为对应的索引（'a' -> 0, 'b' -> 1, ..., 'z' -> 25）
}
// 统计 str2 中前 n 个字符的频率，n 为 str1 的长度
for (int i = 0; i < str1.length(); i++) {
windowCount[str2.charAt(i) - 'a']++; // 更新窗口字符频率
}
// 如果初始窗口中的字符频率已经匹配，直接返回 0（表示从第 0 位开始符合条件）
if (matches(targetCount, windowCount)) {
return 0;
}
// 从 str2 中第 n 个字符开始，滑动窗口
for (int i = str1.length(); i < str2.length(); i++) {
// 更新窗口，移除最左边的字符，添加新的字符
windowCount[str2.charAt(i - str1.length()) - 'a']--; // 移除最左边的字符
windowCount[str2.charAt(i) - 'a']++; // 添加新的字符
// 检查更新后的窗口字符频率是否与 str1 的字符频率匹配
if (matches(targetCount, windowCount)) {
return i - str1.length() + 1; // 返回窗口的起始位置
}
}
// 如果遍历完所有窗口都没有找到匹配的子串，返回 -1
return -1;
}
// matches 方法用于比较两个字符频率数组是否完全相同
private static boolean matches(int[] targetCount, int[] windowCount) {
for (int i = 0; i < 26; i++) {
if (targetCount[i] != windowCount[i]) { // 如果某个字符的频率不匹配
return false; // 返回 false
}
}
return true; // 所有字符频率匹配，返回 true
}
}
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">字符计数：首先统计 str1 中每个字符的频率，存储在 targetCount 数组中。接着使用滑动窗口的方法遍历 str2，统计窗口中的字符频率，并存储在 windowCount 数组中。
初始窗口匹配：首先，检查 str2 的前 n 个字符（n 为 str1 的长度）是否与 str1 的字符频率匹配。如果匹配，直接返回起始索引 0。
滑动窗口：将窗口从 str2 的前 n 个字符滑动到后面的字符。每次滑动时，更新 windowCount 数组（即移除窗口最左边的字符并加入新字符）。每次更新后，检查窗口中的字符频率是否与 str1 的频率相匹配。如果匹配，返回当前窗口的起始位置。
结束条件：如果遍历完所有窗口仍未找到匹配的子串，则返回 -1。
#include 解题思路
这道题要求我们在字符串 str2 中查找是否有一个与字符串 str1 字母排列相同的子串，并返回第一个符合条件子串的起始位置。我们可以通过 滑动窗口 和 字符计数 技巧来高效地实现该功能。
步骤解析：
字符计数：
我们将 str1 中的每个字符的频率存储在 count1 数组中。
同样，我们将 str2 中当前窗口的字符频率存储在 count2 数组中。
初始窗口：
初始化滑动窗口为 str2 中的前 len1 个字符（即 str1 的长度），并将其字符频率存储在 count2 中。
滑动窗口：
从 str2 的第一个字符开始，滑动窗口每次向右移动一个字符。每移动一步：
移除窗口最左边的字符（即 s2[i-1]），并添加新的字符（即 s2[i + len1 - 1]）。
比较 count1 和 count2 是否相等，如果相等，说明当前窗口是 str1 的字母排列，返回当前窗口的起始位置。
结束条件：
如果找到了符合条件的子串，则返回其起始索引；如果遍历整个 str2 后都未找到，则返回 -1。
#include 解题思路
这道题目要求在字符串 str2 中查找是否有一个与字符串 str1 字母排列相同的子串，并返回第一个符合条件子串的起始位置。我们可以使用 滑动窗口 和 字符计数 技巧来高效地实现该功能。
思路概述：
字符计数：
通过两个字符计数数组，count1 用于统计 str1 中每个字符的频率，count2 用于统计 str2 中当前滑动窗口内每个字符的频率。
初始窗口：
初始化滑动窗口为 str2 中的前 len1 个字符（即 str1 的长度），并将其字符频率存储在 count2 数组中。
滑动窗口：
从 str2 的第一个字符开始，滑动窗口每次向右移动一个字符。每移动一步：
移除窗口最左边的字符（即 s2[i - str1.length]），并添加新的字符（即 s2[i]）。
比较 count1 和 count2 是否相等，如果相等，说明当前窗口是 str1 的字母排列，返回当前窗口的起始位置。
结束条件：
如果找到了符合条件的子串，则返回其起始索引；如果遍历整个 str2 后都未找到，则返回 -1。
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
// 监听输入行，获取用户输入
rl.on("line", (line) => {
// 将输入的两个字符串按空格分割
let [str1, str2] = line.split(" ");
// 调用 findSubstring 函数并输出结果
console.log(findSubstring(str1, str2));
});
// 主逻辑函数：查找 str2 中与 str1 字母排列相同的子串
function findSubstring(str1, str2) {
// 初始化两个长度为 26 的数组用于记录字母的出现频率
const count1 = Array(26).fill(0); // str1 中字符的频率
const count2 = Array(26).fill(0); // 当前滑动窗口中字符的频率
// 统计 str1 中每个字符的频率
for (let i = 0; i < str1.length; i++) {
count1[str1.charCodeAt(i) - 97]++; // 'a' 的 ASCII 值是 97，所以使用 `charCodeAt(i) - 97` 得到字母对应的数组索引
}
// 统计 str2 中前 len1 个字符的频率
for (let i = 0; i < str1.length; i++) {
count2[str2.charCodeAt(i) - 97]++;
}
// 如果 str1 和 str2 的前 len1 个字符的频率相同，直接返回 0
if (arraysEqual(count1, count2)) return 0;
// 滑动窗口，从 str2 的第 len1 个字符开始滑动
for (let i = str1.length; i < str2.length; i++) {
// 移除窗口最左边的字符
count2[str2.charCodeAt(i - str1.length) - 97]--;
// 添加新字符到窗口
count2[str2.charCodeAt(i) - 97]++;
// 如果当前窗口的字符频率与 str1 相同，返回当前窗口的起始索引
if (arraysEqual(count1, count2)) return i - str1.length + 1;
}
// 如果没有找到符合条件的子串，返回 -1
return -1;
}
// 辅助函数：判断两个字符频率数组是否相等
function arraysEqual(arr1, arr2) {
for (let i = 0; i < 26; i++) {
if (arr1[i] !== arr2[i]) return false; // 如果有任何位置的字符频率不同，返回 false
}
return true; // 如果所有位置的字符频率相同，返回 true
}
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏
评论记录：
回复评论：