Find the First Anagram Window in a String

## Problem Given a lookup string and a nonempty query string, return the starting index of the first contiguous substring of the lookup string that is an anagram of the query. Return `-1` if no such substring exists. Two strings are anagrams when every character has the same frequency in both strings. The selected substring must have exactly the same length as the query. ### Function Contract Implement `firstAnagramIndex(lookup, query)` and return one integer. ### Constraints & Assumptions - `1 <= len(query) <= 200,000` and `0 <= len(lookup) <= 200,000`. - Both strings contain lowercase English letters only. - If several windows match, return the smallest starting index. - The target time complexity is `O(len(lookup) + len(query))`. ### Clarifying Questions to Ask - Is matching case-sensitive? Yes; inputs are already normalized to lowercase. - May the matching letters be nonconsecutive? No, they must occupy one contiguous window. - What happens when the query is longer than the lookup? Return `-1`. - Does the first match mean the first window in left-to-right order? Yes. ```hint Compare frequency state, not sorted windows Sorting every window repeats work. Build the query counts once and update only the two characters that change when the window advances. ``` ```hint Track whether all counts balance A fixed array of 26 differences is enough. You may compare that array at each step or maintain the number of nonzero positions as counts change. ``` ### Examples ```text lookup = "databricks", query = "tad" -> 0 lookup = "databricks", query = "bar" -> 3 lookup = "databricks", query = "cat" -> -1 lookup = "cbaebabacd", query = "abc" -> 0 ``` ### Evaluation Focus - Initializes the first window correctly and checks it before sliding. - Removes the outgoing character and adds the incoming character exactly once. - Returns the earliest matching index, including index `0`. - Handles repeated letters in the query. - Uses `O(1)` auxiliary space for the fixed alphabet. ### Extensions to Discuss 1. How would the implementation change for arbitrary Unicode characters? 2. How could the function process a lookup string delivered as a stream? 3. What changes if all matching indices must be returned?