题目描述

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

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

思路

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

题目内容

给定两个字符串$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$