Katkat
Back

Find start indices of anagram substrings

TikTokSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates proficiency in string processing, frequency-based pattern matching, and algorithmic efficiency under length constraints, testing the ability to reason about time and space trade-offs for substring searches.

You are given two strings:

  • s: the text string
  • p: the pattern string

Return a list of all starting indices i such that the substring s[i : i + len(p)] is a permutation (an anagram) of p. The indices can be returned in increasing order.

Input

  • s and p contain only lowercase English letters.

Output

  • An array/list of integers: all valid starting indices.

Examples

  1. s = "cbaebabacd", p = "abc" → [0, 6]
  • s[0:3] = "cba" is an anagram of "abc"
  • s[6:9] = "bac" is an anagram of "abc"
  1. s = "abab", p = "ab" → [0, 1, 2]

Constraints

  • 1 <= len(s) <= 3 * 10^4
  • 1 <= len(p) <= 3 * 10^4
  • len(p) <= len(s)