Skip to main content

Sliding Window

Find All Anagrams in a String Solution In C++/Java/Python/JS

Problem Description

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

What is an Anagram?

An Anagram is when two words contain the exact same characters with the same frequency, just arranged in a different order.

Examples

  1. "listen" and "silent"
  • Both have the same letters: l, i, s, t, e, n
  • Just rearranged
  • Both are Anagrams
  1. "hello" and "helloo"
  • "helloo" has an extra ‘o’
  • Both are not Anagrams

Examples

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

Constraints

  • 1 <= s.length, p.length <= 3 * 10^4
  • s and p consist of lowercase English letters.
💡
Try it Yourself First
The very first question that comes to our mind after reading the problem is: How can we identify anagrams of the pattern string p within the main string s? Most of us already know that one straightforward way is to examine every possible substring of s and check if it forms an anagram of p. To build a solid understanding, let's start by exploring this brute-force approach in detail. This will help us grasp the core concept clearly before moving on to more optimized solutions.

Brute-Force Approach

Intuition

Since we want to find all substrings in s that are anagrams of p, the first idea that comes to our mind is to generate all substrings of s that are of the same length as p. For example, if p has length 3, then we go through the string s and take out all possible substrings of length 3 starting from each index.

Why Exactly Substrings of the Same Length of p?

An anagram is a word that contains exactly the same letters as another word. So, if the original word p has 3 letters, then its anagram must also have exactly 3 letters—not more, not less. If we check substrings of different lengths, they can't possibly match the pattern p in terms of both letters and frequency. For example, an anagram of "abc" must be 3 characters long, and it must include only the letters a, b, and c, just shuffled in some way.

For this, we can use a nested loop. The outer loop will fix the starting index of the substring, and the inner loop will help us build substrings of the same length as p from that starting point.

Generating Substrings of Length p using Nested Loops

To implement this, we first fix the starting index i of the substring in s using an outer loop. This loop runs from i = 0 up to i = s.length() - p.length(), ensuring that only valid substrings of length equal to p are considered.

For each fixed starting index i, we use an inner loop with index j to manually build the substring. This inner loop runs from j = i to j < i + p.length(). We start with an empty string sub and append characters from s[j] one by one. This manual construction of substrings helps beginners understand how substrings can be formed using indices, without relying on built-in substring functions.
Note: We can also replace the inner loop and use built-in substring methods instead.

Let’s consider an example to clarify this process. Suppose s = "cbaebabacd" and p = "abc", where p.length() = 3. Using the loops:

  • At i = 0, the inner loop collects s[0], s[1], s[2] resulting in substring "cba"
  • At i = 1, the inner loop collects s[1], s[2], s[3] resulting in substring "bae"
  • At i = 2, the inner loop collects s[2], s[3], s[4] resulting in substring "aeb"
  • At i = 3, the inner loop collects s[3], s[4], s[5] resulting in substring "eba"
  • At i = 4, the inner loop collects s[4], s[5], s[6] resulting in substring "bab"
  • At i = 5, the inner loop collects s[5], s[6], s[7] resulting in substring "aba"
  • At i = 6, the inner loop collects s[6], s[7], s[8] resulting in substring "bac"
  • At i = 7, the inner loop collects s[7], s[8], s[9] resulting in substring "acd"

Each substring is exactly 3 characters long, matching the length of p. After extracting these substrings, we can proceed to check if any of them are anagrams of p.

Once we have a substring from s, the next task is to check whether it is an anagram of p. Now here’s a clever observation: since anagrams have the exact same characters with the same frequency, if we sort both the substring and p, the sorted versions should be exactly the same. For example, "abc", "bca" and "cab" are anagrams. When sorted, all will become "abc".

  • "abc" → sorted → "abc"
  • "bca" → sorted → "abc"
  • "cab" → sorted → "abc"

So, to check whether a substring is an anagram of p, we sort both and compare them. If they are equal, then this substring is indeed an anagram of p, and we store its starting index.
We repeat this process for all substrings of length equal to length of p and collect the indices where the substring is an anagram. Finally, we return the list of all these starting indices.

Approach

Step 1: Sort the Pattern String p
Before we start checking any substrings in s, we sort the string p once and store it. This sorted version acts as our reference point. Every time we create a substring from s, we will sort it and compare it with this sorted pattern. If they match, we can confidently say that the substring is an anagram of p.
Sorting is done only once for p, which saves us from unnecessary repetition and gives us a fixed target to compare with.

Step 2: Loop Through String s to Fix the Starting Index i
We use an outer loop that moves through every valid starting position i in the string s, such that a complete substring of length p can be formed starting at i.

The loop runs from: i = 0 to i <= s.length() - p.length()

This ensures we only consider substrings that are exactly the same length as p.

Step 3: Use Inner Loop to Manually Construct the Substring
For every starting index i, we use an inner loop with index j to build the substring character by character.

This loop runs from j = i to j < i + p.length().

We initialize an empty string sub and keep appending characters from s[j] into sub.
This step simulates how substrings are manually constructed using a loop, which helps in understanding string manipulation using indices—especially useful for beginners who want to learn how substrings are built without relying on library functions.

Step 4: Sort the Constructed Substring and Compare with Sorted p
Once the substring is formed, we sort it. We then compare this sorted substring with our previously sorted version of p.
If both are equal, it means that the characters and their frequencies are exactly the same, which is the definition of an anagram.

Step 5: If It Matches, Store the Starting Index i
If the sorted substring matches the sorted pattern, we store the current starting index i in our result list.
This index represents the starting position of an anagram of p in s.

Step 6: After the Loops, Return the Result List
After the outer loop has finished checking all possible substrings in s, we return the result vector. This contains all the starting indices where an anagram of p was found in s.

Dry Run

Let's do a detailed dry run of the brute-force approach using nested loops and sorting for the input:
s = "cbaebabacd", p = "abc"

We want to find all starting indices in s where the substring is an anagram of p.

Step 1: Preprocessing
We begin by sorting the string p.

  • Original p = "abc"
  • Sorted p = "abc"

This sorted string will be used as our reference to check whether any substring of s is an anagram of p.

Step 2: Loop Over s to Check All Substrings of Length p.length()
The length of p is 3, so we want to extract every substring of s that is exactly 3 characters long. The loop will go from: i = 0 to i = s.length() - p.length() = 10 - 3 = 7

At each index i, we will:

  • Use a nested loop from j = i to j < i + 3 to build the substring manually.
  • Sort the built substring.
  • Compare it with the sorted version of p.

Iteration-Wise Dry Run

i = 0
Build substring:

  • j = 0 → sub = "c"
  • j = 1 → sub = "cb"
  • j = 2 → sub = "cba"

Sorted substring = "abc"
Compare with sorted p = "abc" → Match → Store index 0

i = 1
Build substring:

  • j = 1 → sub = "b"
  • j = 2 → sub = "ba"
  • j = 3 → sub = "bae"

Sorted substring = "abe"
Compare with "abc" → Not a match→ Do not store

i = 2
Build substring:

  • j = 2 → sub = "a"
  • j = 3 → sub = "ae"
  • j = 4 → sub = "aeb"

Sorted substring = "abe"
Compare with "abc" → Not a match → Do not store

i = 3
Build substring:

  • j = 3 → sub = "e"
  • j = 4 → sub = "eb"
  • j = 5 → sub = "eba"

Sorted substring = "abe"
Compare with "abc" → Not a match→ Do not store

i = 4
Build substring:

  • j = 4 → sub = "b"
  • j = 5 → sub = "ba"
  • j = 6 → sub = "bab"

Sorted substring = "abb"
Compare with "abc" → Not a match → Do not store

i = 5
Build substring:

  • j = 5 → sub = "a"
  • j = 6 → sub = "ab"
  • j = 7 → sub = "aba"

Sorted substring = "aab"
Compare with "abc" → Not a match→ Do not store

i = 6
Build substring:

  • j = 6 → sub = "b"
  • j = 7 → sub = "ba"
  • j = 8 → sub = "bac"

Sorted substring = "abc"
Compare with "abc" → Match→ Store index 6

i = 7
Build substring:

  • j = 7 → sub = "a"
  • j = 8 → sub = "ac"
  • j = 9 → sub = "acd"

Sorted substring = "acd"
Compare with "abc" → Not a match → Do not store

Final Result
The indices where we found substrings that are anagrams of "abc": Result = [0, 6]

These correspond to:

  • s[0..2] = "cba" → anagram of "abc"
  • s[6..8] = "bac" → anagram of "abc"
Code for All Languages
C++ 
#include <iostream> // For input and output functions like cin and cout
#include <vector> // For using the vector data structure
#include <string> // For using string operations
#include <algorithm> // For using the sort function
using namespace std;

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> result;

        int sLength = s.length();
        int pLength = p.length();

        // Step 1: Sort the pattern string 'p' once
        string sortedP = p;
        sort(sortedP.begin(), sortedP.end());

        // Step 2: Outer loop to fix the starting index 'i'
        for (int i = 0; i <= sLength - pLength; i++) {
            string sub = "";

            // Step 3: Inner loop to build the substring manually from i to i + pLength - 1
            for (int j = i; j < i + pLength; j++) {
                sub.push_back(s[j]);
            }

            // Step 4: Sort the manually constructed substring
            sort(sub.begin(), sub.end());

            // Step 5: Compare sorted substring with sorted pattern string
            if (sub == sortedP) {
                result.push_back(i); // Store the starting index if it's an anagram
            }
        }

        // Step 6: Return the list of starting indices where anagrams were found
        return result;
    }
};

int main() {
    string s, p;

    // Input the main string and the pattern string (no prompt as requested)
    cin >> s >> p;

    Solution sol;
    vector<int> indices = sol.findAnagrams(s, p);

    // Output the resulting indices
    for (int index : indices) {
        cout << index << " ";
    }

    return 0;
}

Java 
import java.util.*; // For List, ArrayList, Scanner, and Arrays.sort()

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();

        int sLength = s.length();
        int pLength = p.length();

        // Step 1: Sort the pattern string 'p' once
        char[] pArray = p.toCharArray();
        Arrays.sort(pArray);
        String sortedP = new String(pArray);

        // Step 2: Outer loop to fix the starting index 'i'
        for (int i = 0; i <= sLength - pLength; i++) {
            StringBuilder sub = new StringBuilder();

            // Step 3: Inner loop to build the substring manually from i to i + pLength - 1
            for (int j = i; j < i + pLength; j++) {
                sub.append(s.charAt(j));
            }

            // Step 4: Sort the manually constructed substring
            char[] subArray = sub.toString().toCharArray();
            Arrays.sort(subArray);
            String sortedSub = new String(subArray);

            // Step 5: Compare sorted substring with sorted pattern string
            if (sortedSub.equals(sortedP)) {
                result.add(i); // Store the starting index if it's an anagram
            }
        }

        // Step 6: Return the list of starting indices where anagrams were found
        return result;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // Input the main string and the pattern string (no prompt as requested)
        String s = sc.next();
        String p = sc.next();

        Solution sol = new Solution();
        List<Integer> indices = sol.findAnagrams(s, p);

        // Output the resulting indices
        for (int index : indices) {
            System.out.print(index + " ");
        }
    }
}

Python 
from typing import List  # For specifying the return type as a list of integers

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        result = []

        sLength = len(s)
        pLength = len(p)

        # Step 1: Sort the pattern string 'p' once
        sorted_p = ''.join(sorted(p))

        # Step 2: Outer loop to fix the starting index 'i'
        for i in range(sLength - pLength + 1):
            sub = ''

            # Step 3: Inner loop to manually build the substring from i to i + pLength - 1
            for j in range(i, i + pLength):
                sub += s[j]

            # Step 4: Sort the manually constructed substring
            sorted_sub = ''.join(sorted(sub))

            # Step 5: Compare sorted substring with sorted pattern string
            if sorted_sub == sorted_p:
                result.append(i)  # Store the starting index if it's an anagram

        # Step 6: Return the list of starting indices where anagrams were found
        return result

# Driver Code
if __name__ == "__main__":
    s = input()  # Input the main string
    p = input()  # Input the pattern string

    sol = Solution()
    indices = sol.findAnagrams(s, p)

    # Output the resulting indices
    for index in indices:
        print(index, end=' ')

Javascript 
/**
 * @param {string} s - The main text string
 * @param {string} p - The pattern string to find anagrams of
 * @return {number[]} - Array of starting indices where anagrams of p begin in s
 */
var findAnagrams = function(s, p) {
    let result = [];

    let sLength = s.length;
    let pLength = p.length;

    // Step 1: Sort the pattern string 'p' once
    let sortedP = p.split('').sort().join('');

    // Step 2: Outer loop to fix the starting index 'i'
    for (let i = 0; i <= sLength - pLength; i++) {
        let sub = '';

        // Step 3: Inner loop to build the substring manually from i to i + pLength - 1
        for (let j = i; j < i + pLength; j++) {
            sub += s[j];
        }

        // Step 4: Sort the manually constructed substring
        let sortedSub = sub.split('').sort().join('');

        // Step 5: Compare sorted substring with sorted pattern string
        if (sortedSub === sortedP) {
            result.push(i); // Store the starting index if it's an anagram
        }
    }

    // Step 6: Return the list of starting indices where anagrams were found
    return result;
};

// Driver code
const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let inputs = [];

rl.on("line", function(line) {
    inputs.push(line.trim());
    if (inputs.length === 2) {
        const s = inputs[0];
        const p = inputs[1];

        const indices = findAnagrams(s, p);
        console.log(indices.join(' '));

        rl.close();
    }
});

Time Complexity: O(n * m log(m))

Outer Loop: O(n - m + 1)
The outer loop runs from index i = 0 to i = s.length() - p.length().
Let’s denote:

  • n = length of the string s
  • m = length of the pattern p
    So, the loop executes approximately (n - m + 1) times, which is O(n) in the worst case.

Inner Loop: O(m)
For each iteration of the outer loop, we manually build a substring of length m using an inner loop from j = i to j < i + m.
This takes O(m) time per outer iteration.

Sorting the Substring: O(m log m)
After building the substring, we sort it.
Sorting a string of length m takes O(m log m) time.

Comparing with Sorted p: O(m)
After sorting, we compare the substring with the pre-sorted version of p, which takes O(m) time.

Total Time per Outer Loop Iteration: O(m log m)
The substring building, sorting, and comparison together cost
O(m + m log m + m) = O(m log m).

Final Time Complexity: O(n * m log m)

We perform O(m log m) operations for each of the O(n) positions in the string s.
So, the total time complexity is: O(n * m log m)
Where:

  • n is the length of string s
  • m is the length of string p

Space Complexity: O(m)

Auxiliary Space Complexity: O(m)
This refers to any extra space used by the algorithm that is independent of the input and output space.
In our brute-force approach, we create:

  • A temporary substring of length m (where m is the length of pattern p) for each iteration.
  • A sorted version of the substring, and also a sorted version of p (which we compute once and reuse).
  • A result list to store the starting indices.

The temporary substring and sorted version are recreated in each iteration and use space proportional to m.
Therefore, the auxiliary space used in one iteration is O(m), and this doesn't grow beyond that.
Hence, the auxiliary space complexity is O(m).

Total Space Complexity: O(n + m)
This includes the space required for:

  • Input space: The input strings s and p are of lengths n and m respectively. So, input space is O(n + m).
  • Output space: We store the resulting starting indices in a list. In the worst case, there could be up to n - m + 1 indices, which is O(n).
  • Extra space used by the algorithm: As analyzed above, O(m).

Combining all the space requirements:

Total Space Complexity = O(n + m) + O(n) + O(m) = O(n + m)

Why this Approach will give TLE?

The main reason this approach is slow and can time out is because of its high time complexity combined with the input size constraints.

  • The length of the string s and pattern p can be as large as 30,000 (3 * 10^4), then:
  • Sorting each substring takes O(m log m) , which is about 30,000 * log(30,000) ≈ 30,000 * 15 = 450,000 operations.
  • Doing this for all n ≈ 30,000 starting points means roughly: 30,000 (n) * 450,000 (m log m) = 13,500,000,000 operations

This is over 13 billion operations, which is far too large to complete within typical time limits (usually 1-3 seconds).

Most competitive programming platforms like LeetCode or Codeforces set a time limit of 1-2 seconds for a program to run or 10^7 operations per second.

For large inputs, this can easily cross the allowed operation limit, causing Time Limit Exceeded.

We have seen the brute-force solution, which taught us how to check for anagrams by sorting. However, sorting each substring costs us O(m log m), which can be quite expensive. Can we do better by leveraging the properties of anagrams? Is it possible to eliminate the nested loops and improve the time complexity? Let’s find out as we move on to the optimal approach.

Optimal Approach

Intuition

Let’s pause and reflect on what an anagram really is. An anagram of a string contains exactly the same characters, in exactly the same quantity, just possibly in a different order. For example, "abc", "bca", and "cab" are all anagrams of each other. Now think carefully — if order doesn't matter, then comparing sorted strings is just a clever hack to check whether two strings have the same characters. But there’s an even better way: use frequency counting.

Since we’re only dealing with lowercase English letters (a–z), we know there are only 26 characters possible. We can create an array of size 26 to store the frequency of each character also called as a frequency Array.

What is a Frequency Array?

A frequency array is just a way to count how many times each element appears — usually characters in a string or numbers in a specific range.

Think of it as a table or list that keeps track of how often each item shows up.

Why Do We Need It?
In many string or array problems, we often need to know:

  • How many times a character appears?
  • Are two strings made of the same letters with the same counts? (Anagram check)
  • Is a character missing or extra?

A frequency array helps us answer these questions quickly — and more efficiently than using repeated loops or searches.

How Does It Work?
Let’s take a common example: counting the number of times each lowercase letter appears in a string.

There are 26 lowercase letters (a to z), so we prepare an array of size 26.

Each index of this array represents a letter:

  • Index 0 for 'a'
  • Index 1 for 'b'
    …
  • Index 25 for 'z'

Every time we see a letter, we just increase the count at that index.
Similarly, if we’re working with numbers from 0 to 9, we could use an array of size 10 — each index representing a number.

Example
Suppose we’re given the word: "aabbc"

We create a frequency array of size 26 (for letters ‘a’ to ‘z’), all initialized to 0.

Now we go through the word:

  • See 'a' → increase count at index 0 → becomes 1
  • See 'a' again → increase count at index 0 → becomes 2
  • See 'b' → index 1 → becomes 1
  • See 'b' again → index 1 → becomes 2
  • See 'c' → index 2 → becomes 1

Final frequency array:

  • Index: 0 1 2 3 4 ...
  • Letter: a b c d e ...
  • Value: 2 2 1 0 0 ...

This tells us:

  • 'a' appears 2 times
  • 'b' appears 2 times
  • 'c' appears 1 time
  • Others are not present (0)

What Makes it Powerful?

  • Instant access: We can access or update any letter’s count in O(1) time.
  • No hash maps needed: For simple problems (especially limited to lowercase letters), we don’t need hash maps or dictionaries.
  • Very space-efficient: Just 26 slots to cover all lowercase letters.

So here’s the idea:

  • We'll first count how many times each character appears in p. This becomes our reference.
  • Next, we slide a window over s of the same length as p. For each such window (which is just a substring), we count the frequencies of characters in that window as well.
  • If the frequency array of the window matches the frequency array of p, we’ve found an anagram.

What is Sliding Window Technique?

Imagine you’re looking at a long line of items — like numbers in an array or letters in a string — and you want to examine small parts (subarrays or substrings) of it one at a time.

The Sliding Window Technique helps us do this efficiently, without starting over every time.

Instead of recalculating everything from scratch for each part, we slide a “window” over the data, reusing most of the previous work.

What is a “Window”?

A window is just a small segment or a range within the array or string.

For example:
Let’s say we have this array: arr = [1, 2, 3, 4, 5, 6]

If we want to look at subarrays of size 3:

  • First window: [1, 2, 3]
  • Next window: [2, 3, 4]
  • Then: [3, 4, 5], and so on...

Each time, we just move the window one step forward, dropping the first element and including the next.

Why Do We Use It?

Because it's efficient!

Let’s say we wanted the sum of each window of size 3:

Naive Way (Brute Force):

  • For every window, loop through the 3 elements and sum them → O(n * k), where n = length of array, k = window size.

Sliding Window Way:

Sum the first window once. For the next window:

  • Subtract the element going out of the window.
  • Add the element coming in.

This makes each new window sum in O(1) time → total O(n).

Types of Sliding Windows

There are mainly two types:

1. Fixed-size Sliding Window - Window size stays the same.

2. Variable-size Sliding Window - The window grows or shrinks based on conditions.

In this problem, we are using fixed size Sliding Window as the window size if fixed, i.e. length of p.

Now let’s talk about how to make this process efficient. At first, we build the frequency array for the first window in s (i.e., the first p.length() characters). After that, instead of recalculating the frequency array from scratch for every new window, we slide the window by just one character at a time. That means:

  • We subtract the frequency of the character that is moving out of the window.
  • We add the frequency of the character that is coming into the window.

This is extremely efficient because we’re only doing constant time updates to the frequency array — no full rebuilds, no sorting. We’re making O(1) changes as we move from one window to the next.

And comparing the two frequency arrays — the one for p and the current window in s — is also quick. Since the arrays are always of length 26, comparing them takes constant time too.

Approach

Step 1: Prepare Frequency Arrays for the Pattern and the First Window
Before we start checking for anagrams, we build frequency arrays of size 26 (for all lowercase letters).

  • One array pFreq stores the frequency of characters in the pattern string p.
  • Another array sFreq stores the frequency of characters in the current window of string s.

We initialize both by:

  • Looping through the first p.length() characters.
  • For each character, increase its corresponding count in both pFreq and sFreq.

This sets up the initial state to compare the pattern with the first window of the main string.

Step 2: Slide the Window Over the String s
Now we begin checking all substrings (or windows) of length equal to p.length() by sliding the window one character at a time.
We use a loop from i = 0 to i <= s.length() - p.length(). This ensures the last window considered is fully within bounds.
At each position i, we compare the frequency arrays pFreq and sFreq.
If they are equal, it means the substring from i to i + p.length() - 1 is an anagram of p, so we store the index i.

Step 3: Shift the Window by One Character
After comparing the current window:

  • We remove the character going out of the window (i.e., s[i]) by decrementing its count in sFreq.
  • We add the character coming into the window (i.e., s[i + p.length()]) by incrementing its count in sFreq.

We only do this update if i + p.length() < s.length() to avoid accessing out-of-bounds characters.

Step 4: Return the Result
Once the loop completes, we return the list of stored indices. These indices represent the starting positions of all substrings in s that are anagrams of p.

Dry Run

Let’s do a step-by-step dry run of the optimized sliding window + hashing approach for the input:

  • s = "cbaebabacd"
  • p = "abc"

We aim to find all starting indices in s where an anagram of p begins.

Step 1: Prepare Frequency Arrays for Pattern and First Window

We create two arrays of size 26 (for each lowercase English letter):

  • pFreq[]: frequency of characters in the pattern p
  • sFreq[]: frequency of characters in the current window of s

Since p = "abc", we loop through the first 3 characters of both strings:

pFreq for "abc" = [1, 1, 1, 0, ..., 0]
sFreq for "cba" = [1, 1, 1, 0, ..., 0]

Both frequency arrays match initially.

Step 2: Slide the Window Over String s

We use a loop from i = 0 to i = s.length() - p.length() = 7

At each iteration:

Compare pFreq and sFreq. If they match, we add i to our result. Then we slide the window forward by:

  • Removing s[i] from sFreq
  • Adding s[i + p.length()] to sFreq

Dry Run Iterations

i = 0

  • Current window: "cba"
  • pFreq == sFreq → Match
    Store index 0

Update Window:

  • Remove 'c' → Decrement index 2
  • Add 'e' → Increment index 4

i = 1

  • Current window: "bae"
  • pFreq != sFreq → No match

Update Window:

  • Remove 'b', Add 'b'

i = 2

  • Current window: "aeb"
  • pFreq != sFreq → No match

Update Window:

  • Remove 'a', Add 'a'

i = 3

  • Current window: "eba"
  • pFreq != sFreq → No match

Update Window:

  • Remove 'e', Add 'b'

i = 4

  • Current window: "bab"
  • pFreq != sFreq → No match

Update Window:

  • Remove 'b', Add 'a'

i = 5

  • Current window: "aba"
  • pFreq != sFreq → No match

Update Window:

  • Remove 'a', Add 'c'

i = 6

  • Current window: "bac"
  • pFreq == sFreq → Match
    Store index 6

Update Window:

  • Remove 'b', Add 'd'

i = 7

  • Current window: "acd"
  • pFreq != sFreq → No match

Final Result

Stored indices: [0, 6]

These correspond to the substrings:

  • s[0..2] = "cba" → anagram of "abc"
  • s[6..8] = "bac" → anagram of "abc"
Code for All Languages
C++ 
#include <iostream>    // For input and output functions like cin and cout
#include <vector>      // For using the vector data structure
#include <string>      // For using string operations
using namespace std;

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> result;
        int sLength = s.length();
        int pLength = p.length();

        // Frequency arrays for pattern 'p' and current window in 's'
        vector<int> pFreq(26, 0);  // Frequency of characters in p
        vector<int> sFreq(26, 0);  // Frequency of characters in current window of s

        // Step 1: Build frequency count for pattern p
        for (int i = 0; i < pLength; i++) {
            pFreq[p[i] - 'a']++;
            sFreq[s[i] - 'a']++;  // Also fill first window of s
        }

        // Step 2: Slide the window over string s
        for (int i = 0; i <= sLength - pLength; i++) {
            // If current window's frequency matches pattern's frequency, it's an anagram
            if (pFreq == sFreq) {
                result.push_back(i);
            }

            // Move the window one step forward:
            // Remove the character going out of the window
            if (i + pLength < sLength) {
                sFreq[s[i] - 'a']--;                   // Remove s[i]
                sFreq[s[i + pLength] - 'a']++;         // Add s[i + pLength]
            }
        }

        return result;
    }
};

int main() {
    string s, p;

    // Input the main string and the pattern string (no prompt as requested)
    cin >> s >> p;

    Solution sol;
    vector<int> indices = sol.findAnagrams(s, p);

    // Output the resulting indices
    for (int index : indices) {
        cout << index << " ";
    }

    return 0;
}

Java 
import java.util.*; // For List, ArrayList, Scanner

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();

        int sLength = s.length();
        int pLength = p.length();

        // Step 1: Frequency arrays for pattern 'p' and current window in 's'
        int[] pFreq = new int[26]; // Frequency of characters in p
        int[] sFreq = new int[26]; // Frequency of characters in current window of s

        // Step 2: Fill the frequency for p and the first window of s
        for (int i = 0; i < pLength; i++) {
            pFreq[p.charAt(i) - 'a']++;
            sFreq[s.charAt(i) - 'a']++;
        }

        // Step 3: Start sliding the window over s
        for (int i = 0; i <= sLength - pLength; i++) {
            // If both frequency arrays match, it's an anagram
            if (Arrays.equals(pFreq, sFreq)) {
                result.add(i);
            }

            // Step 4: Slide the window
            if (i + pLength < sLength) {
                sFreq[s.charAt(i) - 'a']--; // Remove the character going out of the window
                sFreq[s.charAt(i + pLength) - 'a']++; // Add the character coming into the window
            }
        }

        return result;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // Input the main string and the pattern string (no prompt as requested)
        String s = sc.next();
        String p = sc.next();

        Solution sol = new Solution();
        List<Integer> indices = sol.findAnagrams(s, p);

        // Output the resulting indices
        for (int index : indices) {
            System.out.print(index + " ");
        }
    }
}

Python 
from typing import List  # For specifying the return type as a list of integers

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        result = []
        sLength = len(s)
        pLength = len(p)

        # Edge case: If pattern is longer than s, return empty list
        if sLength < pLength:
            return result

        # Step 1: Initialize frequency arrays for p and the current window of s
        pFreq = [0] * 26  # Frequency of characters in p
        sFreq = [0] * 26  # Frequency of characters in current window of s

        # Step 2: Fill the frequency arrays for pattern p and the first window of s
        for i in range(pLength):
            pFreq[ord(p[i]) - ord('a')] += 1
            sFreq[ord(s[i]) - ord('a')] += 1

        # Step 3: Start sliding the window
        for i in range(sLength - pLength + 1):
            # If current window matches pattern frequency, it's an anagram
            if sFreq == pFreq:
                result.append(i)

            # Step 4: Slide the window forward by 1 character
            if i + pLength < sLength:
                sFreq[ord(s[i]) - ord('a')] -= 1  # Remove the character going out
                sFreq[ord(s[i + pLength]) - ord('a')] += 1  # Add the new character

        # Step 5: Return result list containing all valid starting indices
        return result

# Driver Code
if __name__ == "__main__":
    s = input()  # Input the main string
    p = input()  # Input the pattern string

    sol = Solution()
    indices = sol.findAnagrams(s, p)

    # Output the resulting indices
    for index in indices:
        print(index, end=' ')

Javascript 
/**
 * @param {string} s - The main text string
 * @param {string} p - The pattern string to find anagrams of
 * @return {number[]} - Array of starting indices where anagrams of p begin in s
 */
var findAnagrams = function(s, p) {
    let result = [];

    let sLength = s.length;
    let pLength = p.length;

    // Edge case: if pattern is longer than the string, return empty array
    if (sLength < pLength) return result;

    // Step 1: Create frequency arrays for pattern and sliding window in s
    let pFreq = Array(26).fill(0); // Frequency count of characters in p
    let sFreq = Array(26).fill(0); // Frequency count of current window in s

    // Step 2: Populate initial frequencies for first window and pattern
    for (let i = 0; i < pLength; i++) {
        pFreq[p.charCodeAt(i) - 97]++;
        sFreq[s.charCodeAt(i) - 97]++;
    }

    // Step 3: Start sliding the window over s
    for (let i = 0; i <= sLength - pLength; i++) {
        // Compare frequency arrays for current window and pattern
        if (arraysEqual(pFreq, sFreq)) {
            result.push(i); // It's an anagram, store the start index
        }

        // Step 4: Slide the window forward
        if (i + pLength < sLength) {
            sFreq[s.charCodeAt(i) - 97]--;              // Remove outgoing char
            sFreq[s.charCodeAt(i + pLength) - 97]++;    // Add incoming char
        }
    }

    return result;
};

// Helper function to compare two frequency arrays
function arraysEqual(arr1, arr2) {
    for (let i = 0; i < 26; i++) {
        if (arr1[i] !== arr2[i]) return false;
    }
    return true;
}

// Driver code
const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let inputs = [];

rl.on("line", function(line) {
    inputs.push(line.trim());
    if (inputs.length === 2) {
        const s = inputs[0];
        const p = inputs[1];

        const indices = findAnagrams(s, p);
        console.log(indices.join(' '));

        rl.close();
    }
});

Time Complexity: O(n)

Outer Loop: O(n - m + 1)
The outer loop runs from index i = 0 to i <= s.length() - p.length().
Let’s denote:

  • n = length of the string s
  • m = length of the pattern p

So, the loop executes approximately (n - m + 1) times, which simplifies to O(n) in the worst case.

Frequency Comparison per Iteration: O(26) = O(1)
In each iteration, we compare the frequency arrays pFreq and sFreq.
Since we are only working with lowercase English letters, the size of each frequency array is 26.
Thus, comparison takes constant time, i.e., O(26) = O(1).

Window Sliding Updates: O(1)
For each step of the sliding window:

  • We decrement the frequency of the character going out.
  • We increment the frequency of the character coming in.

These are simple arithmetic operations on array indices, and they all take O(1) time.

Total Time per Outer Loop Iteration: O(1)
Each iteration includes:

  • Frequency comparison → O(1)
  • Frequency update for sliding window → O(1)

Hence, the total work done per iteration is constant, i.e., O(1).

Final Time Complexity: O(n)
Since we perform O(1) work per iteration, and the outer loop runs O(n) times, the total time complexity becomes: O(n)

Space Complexity: O(1)

Auxiliary Space Complexity: O(1)
This refers to any extra space used by the algorithm that is independent of the input and output sizes.

In this optimized approach, we create:

  • A frequency array pFreq of size 26 for the pattern p.
  • A frequency array sFreq of size 26 for the current sliding window in s.
  • A result list to store the starting indices (not considered part of auxiliary space since it's part of output).

These arrays are of fixed size, since we are dealing with only lowercase English alphabets.
No matter how large s or p is, these arrays always occupy constant space.

Thus, the auxiliary space complexity is O(1).

Total Space Complexity: O(n + m)

This includes space for:

Input Space:

  • The input string s of length n
  • The input string p of length m So, the input space is O(n + m)

Output Space:

  • We store the starting indices of anagrams in a result list.
  • In the worst case, there could be up to n - m + 1 anagram matches.
    So, the output space is O(n) in the worst case.

Auxiliary Space:

  • As analyzed above, it is O(1)

Total Space Complexity = O(n + m) + O(n) + O(1) = O(n + m)

This makes the optimized approach not just time-efficient but also very space-efficient, ideal for large input sizes.

Learning Tip

Now we have successfully tackled this problem, let's try these similar problems.

Maximum Average Subarray I

You are given an integer array nums consisting of n elements, and an integer k.
Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10-5 will be accepted.

Maximum Number of Vowels in a Substring of Given Length

Given a string s and an integer k, return the maximum number of vowel letters in any substring of s with length k. Vowel letters in English are 'a', 'e', 'i', 'o', and 'u'.