Katkat
Back

Solve sliding window, heap, DP, in-place tasks

SalesforceSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to combine sliding window techniques with hash map frequency tracking to identify all starting indices of valid anagrams in a target string.

Problem: Find All Anagram Substrings

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You must implement this using an optimized sliding window approach with a time complexity of O(n), where n is the length of s.

An anagram is a rearrangement of the letters of another string (e.g., "abc" is an anagram of "cba").

Function Signature

def find_anagrams(s: str, p: str) -> list[int]:

Constraints

  • 1 <= s.length, p.length <= 3 * 10^4
  • s and p consist of lowercase English letters.

Example 1

Input: s = "cbaebabacd", p = "abc" Output: [0, 6] Explanation:

  • The substring at index 0 is "cba", which is an anagram of "abc".
  • The substring at index 6 is "bac", which is an anagram of "abc".

Example 2

Input: s = "abab", p = "ab" Output: [0, 1, 2]

Edge Cases

  • If len(p) > len(s), return an empty list.
  • Handle cases where p contains duplicate characters.
  • Ensure the window slides efficiently without re-counting the entire substring at every step.

Hints

Hint 1

Use a frequency array (or hash map) of size 26 to store the counts of characters in `p`.

Hint 2

Maintain a sliding window of length `len(p)` over `s`, updating character counts as you move the window one position at a time.

Hint 3

Compare the window's character frequency map with `p`'s map; if they match, the current starting index is a valid result.

Follow-up questions

  • How would you modify this algorithm if the strings contained Unicode characters instead of just lowercase English letters?
  • Can you optimize the space complexity to use O(1) extra space beyond the fixed-size frequency arrays?
  • If you were asked to find all anagrams in a streaming input, how would your approach change to handle incoming characters one by one?