{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Find All Anagrams in a String – Solution & Complexity

Interview solutions
/
Find All Anagrams in a String

Solution Walkthrough

  1. Step 1: Look for fixed-size windows

    • Every candidate substring must have exactly the same length as p.
    • That makes this a sliding-window problem rather than a variable-size window like minimum cover.

  2. Step 2: Recount each window from scratch

    • For every start index, build a fresh 26-letter frequency array for the substring and compare it with p.
    • This is correct, but it repeats almost all of the counting work between neighboring windows.
    def find_anagrams(s, p):
    if len(p) > len(s):
        return []
    target = [0] * 26
    for char in p:
        target[ord(char) - ord("a")] += 1
    answer = []
    window_length = len(p)
    for start in range(len(s) - window_length + 1):
        counts = [0] * 26
        for index in range(start, start + window_length):
            counts[ord(s[index]) - ord("a")] += 1
        if counts == target:
            answer.append(start)
    return answer

  3. Step 3: Slide one fixed-size window across s

    • Count p once, count the first window once, then update the window in O(1) per move.
    • Because the alphabet size is fixed at 26, comparing the two count arrays is still constant time.

  4. Step 4: Update counts incrementally

    • Add the new right character, remove the old left character, and compare the arrays.
    • Every window is visited exactly once.
    def find_anagrams(s, p):
    if len(p) > len(s):
        return []
    target = [0] * 26
    window = [0] * 26
    for index in range(len(p)):
        target[ord(p[index]) - ord("a")] += 1
        window[ord(s[index]) - ord("a")] += 1
    answer = []
    if window == target:
        answer.append(0)
    for right in range(len(p), len(s)):
        window[ord(s[right]) - ord("a")] += 1
        window[ord(s[right - len(p)]) - ord("a")] -= 1
        if window == target:
            answer.append(right - len(p) + 1)
    return answer

  5. Step 5: Dry run / sliding-window trace

    Trace s = "abab", p = "ab".

    windowindicescounts match?answer
    "ab"[0,1]yes[0]
    slide right -> "ba"[1,2]yes[0,1]
    slide right -> "ab"[2,3]yes[0,1,2]

    Only one character enters and one leaves on each step, so recomputing the full frequency table is unnecessary.

  6. Step 6: Final solution and complexity

    A fixed-size sliding window with 26-letter frequency arrays finds every anagram in linear time and constant extra space.

    def find_anagrams(s: str, p: str) -> list[int]:
    if len(p) > len(s):
        return []
    target = [0] * 26
    window = [0] * 26
    for index in range(len(p)):
        target[ord(p[index]) - ord("a")] += 1
        window[ord(s[index]) - ord("a")] += 1
    answer: list[int] = []
    if window == target:
        answer.append(0)
    for right in range(len(p), len(s)):
        window[ord(s[right]) - ord("a")] += 1
        window[ord(s[right - len(p)]) - ord("a")] -= 1
        if window == target:
            answer.append(right - len(p) + 1)
    return answer

FAQ

See also

Practice Find All Anagrams in a String online (run code in the browser)Longest Substring Without Repeating Characters solution (medium)Minimum Window Substring solution (hard)First Unique Character in a String solution (easy)Group Anagrams solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?