Ebay OA 面试真题解析：查找第一个字母异位词子串的起始位置

Problem Statement

Given two strings A and B, return the 0-based starting index of the first contiguous substring in A that is a permutation (anagram) of B.

If no such substring exists, return -1.

Constraints

• 1 <= length of B <= length of A <= 100,000
• A and B consist entirely of lowercase English letters.

Test Cases

Example 1

Input: A = "cbaebabacd", B = "abc"

Output: 0

Explanation: The substring "cba" starting at index 0 is a permutation of "abc".

这道题要求在字符串 A 中找到第一个与字符串 B 互为字母异位词（anagram）的连续子串，并返回它在 A 中的 0 下标起始位置；如果不存在则返回 -1。由于长度上限可达 10^5，不能用暴力枚举所有子串，通常要用滑动窗口配合 26 个小写字母的频次统计来做：先统计 B 的字符计数，再在 A 上维护一个长度固定为 |B| 的窗口，窗口每右移一步就增减对应字符计数，并比较窗口是否与目标频次一致。样例中 A = "cbaebabacd"、B = "abc"，最前面的窗口 "cba" 就已经匹配，因此答案是 0。