Permutation Search in Strings | Dataford Interview Questions

Your question is Permutation Search in Strings. Start with the requirements on the right.

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

Problem

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 Python string characters.

Constraints

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

Function Signature

def find_permutation_indices(haystack, needle):