Permutation Search in Strings | Dataford Interview Questions

Sumo Logic search components may need to locate every occurrence of a token's anagram inside a large log string. Given strings haystack and needle, return all starting indices where a contiguous substring of haystack is a permutation of needle.

Character order does not matter, but character multiplicity does. Matching is case-sensitive, and repeated matches must all be returned in ascending index order. Do not create and sort each candidate substring.

Formal Specification

Implement find_permutation_indices(haystack, needle).

Input: Two strings, haystack and needle.
Output: A list of integers containing every valid starting index.
Return an empty list if needle is empty or longer than haystack.
Characters are treated as individual string characters.

Constraints

0 <= len(needle) <= len(haystack) <= 10^6
Characters may be arbitrary string characters
Matching is case-sensitive
Return all matching indices in ascending order

Function Signature

def find_permutation_indices(haystack, needle):

Your question is Permutation Search in Strings. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem