BackmediumSliding Window Flipkart Accenture

Find All Anagrams Solution

Problem Statement

Given a string s and a pattern p, find all starting positions in s where p (or its rearrangement) occurs.

Example 1
Input
s = 'gcagtacg', p = 'gca'
Output
[0, 3]

Explanation: Step 1: Create a hashmap to store the frequency of characters in the pattern. The hashmap will be {'g': 1, 'c': 1, 'a': 1}. Step 2: Create a sliding window of size equal to the length of the pattern. Iterate over the string and for each window, calculate the frequency of characters in the window. Step 3: If the frequency of characters in the window is equal to the frequency of characters in the pattern, add the starting position of the window to the result list. Step 4: Return the result list.

Example 2
Input
s = 'abab', p = 'ab'
Output
[0, 1]

Explanation: Step 1: Create a hashmap to store the frequency of characters in the pattern. The hashmap will be {'a': 1, 'b': 1}. Step 2: Create a sliding window of size equal to the length of the pattern. Iterate over the string and for each window, calculate the frequency of characters in the window. Step 3: If the frequency of characters in the window is equal to the frequency of characters in the pattern, add the starting position of the window to the result list. Step 4: Return the result list.

Constraints

  • 1 <= s.length, p.length <= 3 * 10^4
Live Compiler
Loading...
Test Cases & Output
🔒 Sign up to run your code

🚀 Practice this problem

Run code, get AI hints & track streak

Sign Up Free