How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Databricks.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Databricks during technical interviews.

Find all anagram start indices | Databricks Coding Question

Quick Overview

This question evaluates proficiency in string manipulation, algorithmic efficiency, and pattern detection through character frequency analysis, assessing practical competency in handling fixed-length substring comparisons.

hard
Databricks
Coding & Algorithms
Software Engineer

Find all anagram start indices

Company: Databricks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

## Problem Given two strings `s` and `p`, return all starting indices of substrings in `s` that are anagrams (permutations) of `p`. ### Input - `s`: string - `p`: string ### Output - A list of integers: all start indices `i` such that `s[i : i+len(p)]` is an anagram of `p`. - Indices should be returned in increasing order. ### Notes - Treat strings as lowercase English letters unless otherwise specified. ### Example - `s = "cbaebabacd"`, `p = "abc"` - Output: `[0, 6]` - `s[0:3] = "cba"` is an anagram of `"abc"` - `s[6:9] = "bac"` is an anagram of `"abc"` ### Constraints - `1 <= |s|, |p| <= 3 * 10^4` (or similar interview-scale bounds).

Quick Answer: This question evaluates proficiency in string manipulation, algorithmic efficiency, and pattern detection through character frequency analysis, assessing practical competency in handling fixed-length substring comparisons.

Given two strings s and p, return all starting indices of substrings in s that are anagrams of p. A substring is an anagram of p if it contains exactly the same characters with the same frequencies, possibly in a different order. Return the indices in increasing order. If no such substring exists, return an empty list.

Constraints

1 <= len(s), len(p) <= 3 * 10^4
s and p contain only lowercase English letters
Indices must be returned in increasing order

Examples

Input: ("cbaebabacd", "abc")

Expected Output: [0, 6]

Explanation: The substrings "cba" at index 0 and "bac" at index 6 are both anagrams of "abc".

Input: ("abab", "ab")

Expected Output: [0, 1, 2]

Explanation: The windows "ab", "ba", and "ab" are all anagrams of "ab".

Input: ("aaaaa", "aa")

Expected Output: [0, 1, 2, 3]

Explanation: Every substring of length 2 is "aa", which is an anagram of "aa".

Input: ("abc", "abcd")

Expected Output: []

Explanation: p is longer than s, so no valid substring can exist.

Input: ("a", "a")

Expected Output: [0]

Explanation: The only substring is "a", which matches p exactly.

Input: ("xyz", "ab")

Expected Output: []

Explanation: No substring of length 2 in s has the same character counts as "ab".

Loading coding console...

Quick Overview

Find all anagram start indices

Constraints

Examples

Hints