刷题笔记合集🔗

问题描述

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

请返回:

1. 如果str1是str2的关联子串,返回子串在str2中的起始位置(从0开始计数)
2. 如果str1不是str2的关联子串,返回-1
3. 如果有多个符合条件的子串,返回最小的起始位置

输入格式

两个字符串str1和str2,以空格分隔。

输出格式

一个整数,表示子串的起始位置或-1。

数据范围

• 输入的字符串只包含小写字母
• 字符串长度范围[1, 100000]

样例1

输入:

abc efghicbaiii

输出:

5

说明:

• str2包含str1的一种排列组合"cba"
• 该组合在str2中的起始位置为5

样例2

输入:

abc efghiccaiii

输出:

-1

说明:

• str1的所有排列组合(abc、acb、bac、bca、cab、cba)
• str2中都不包含这些组合
• 所以返回-1

题解

这道题目可以使用滑动窗口来解决:

1. 统计str1中每个字符的出现次数
2. 使用大小为str1.length()的滑动窗口在str2上移动:
   • 窗口内字符出现次数与str1完全相同时,找到一个有效位置
   • 窗口移动时更新字符计数
3. 返回找到的最小起始位置,或-1表示未找到

时间复杂度为 ,其中 是str2的长度。

参考代码

# 读取输入
str1, str2 = input().split()

# 统计str1中字符出现次数
count = {}
for c in str1:
    count[c] = count.get(c, 0) + 1

# 记录str1的总字符数
total = len(str1)

# 初始化滑动窗口
for i in range(len(str1)):
    add = str2[i]
    if count.get(add) is not None:
        if count[add] > 0:
            total -= 1
        count[add] -= 1

# 检查初始窗口
if total == 0:
    print(0)
    exit()

# 移动滑动窗口
for i in range(1, len(str2) - len(str1) + 1):
    # 移除窗口左边的字符
    remove = str2[i-1]
    if count.get(remove) is not None:
        if count[remove] >= 0:
            total += 1
        count[remove] += 1
    
    # 添加窗口右边的字符
    add = str2[i + len(str1) - 1]
    if count.get(add) is not None:
        if count[add] > 0:
            total -= 1
        count[add] -= 1
    
    # 检查当前窗口
    if total == 0:
        print(i)
        exit()

print(-1)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str1 =