Articles by FavTutor
  • AI News
  • Data Structures
  • Web Developement
  • AI Code GeneratorNEW
  • Student Help
  • Main Website
No Result
View All Result
FavTutor
  • AI News
  • Data Structures
  • Web Developement
  • AI Code GeneratorNEW
  • Student Help
  • Main Website
No Result
View All Result
Articles by FavTutor
No Result
View All Result
Home Data Structures and Algorithms

Find all Anagrams in a String (C++, Java, Python)

Jatin Chanana by Jatin Chanana
January 30, 2024
Reading Time: 9 mins read
Find all Anagrams in a String
Follow us on Google News   Subscribe to our newsletter

Finding all anagrams in a string is one of the famous problems in Data structure that is often asked in technical interviews. In this article, we will understand this famous problem (also available in leetcode) and explore various approaches to solve it.

Find all Anagrams in a String Problem

First, let’s revise what an anagram is. An anagram is formed when the characters of one string can be rearranged to create another string. Take the words: “rama” and “amar”. The characters in “amar” can be rearranged to form “rama.”

In this problem we are given a string S and a pattern P, the task is to find the starting indices of substrings in S that are anagrams of P.

We will iterate through all possible substrings of S with the same length as P. For each substring, it checks whether the characters can be rearranged to match the characters in P. If a match is found, the starting index of that substring is added to the list of output indices. The final output is the list of starting indices where anagrams of P are present in S.

Let us discuss it with an example:

Input:

S = "favavfvaf" 
P = "fav"

Output:

[0, 3, 5, 6]

Naive Approach: Using Sorting 

In this approach, we will use the concept of sorting the string. Let us understand it better with an example:

String P is “fav,” we can identify anagrams in string S by sorting both the pattern P and its potential anagrams. For instance, the anagrams of P in S are “fav,” “vfa,” and “afv.” When we sort P and its anagrams, they all become “fav.” This helps us to simplify the identification process.

To find anagrams of P in S, we can iterate through all substrings of S, sort each substring, and compare it to the sorted version of P. If they match, the substring is an anagram of P. 

Firstly we will sort P and after sorting P becomes “afv” Then we will iterate over S with a Window equal to P’s length.

After taking that particular substring from the current window (let’s say temp)  we will sort it and if the sorted substring is equal to sorted P then we will push the starting index of the window to our answer array.

Sorted P = “afv”

Window size = 3

Current window substring = “fav”

Sorted substring = “afv”

Window of size 3

Similarly, we will take all windows of size 3

The Time Complexity of using sorting approach for finding all anagrams in a string is O(m log m) + O((n-m+1) * (m + m log m + m)). Because sorting string P takes O(m log m) time, where m is the length of string P and Iterating through all possible substrings of S: The for loop runs (n-m+1) times, where n is the length of string S.

In each iteration, the algorithm builds a temporary substring (temp) of length m, sorts it (O(m log m)), and compares it with the sorted version of P (O(m)).

The Space Complexity of this approach is O(m) because of the sorted string P and the temporary substring (temp) created in each iteration.

Optimized Approach: Hashing + Sliding Window

The best way to find all anagrams in a string is by using hashing with sliding windows. We will use hashing and sliding windows to identify anagrams of a given string P within string S, we can examine every substring of S that has the same length as P. To check an anagram we have to check that a substring contains the same character with the same frequency as those in P. 

Below is the step-by-step guide to using hashing to find all anagrams:

  1. We will keep two arrays to track the frequencies of characters in both string P and the current substring in string S. If these frequency arrays match for a substring, then that substring is an anagram of string P.
  2. To identify substrings of the same length as string P we will maintain a window with a size equal to the length of string P. 
  3. In each iteration, we will include a new character in the window while removing the first character. This ensures that the window length remains constant throughout each iteration.
Example

Window size = Size of P = 3

Hash Table of P
Hash Table of current substring

The hash table of both the current window substring and the hash table of string P are the same.

Hence both are anagrams.

Similarly, take all windows of size 3.

C++ Code

Here is the implementation in C++:

#include <bits/stdc++.h>
using namespace std;

// Function to find starting indices of anagrams of string 'p' in string 's'
vector<int> FindAnagrams(string &s, string &p)
{
    // Vector to store the starting indices of anagrams
    vector<int> ans;

    // Frequency arrays for characters in 'p' and the current window in 's'
    vector<int> arr1(26, 0), arr2(26, 0);

    // Lengths of strings 's' and 'p'
    int n = s.length(), m = p.length();

    // If 'p' is longer than 's', no anagrams are possible
    if (m > n)
        return ans;

    // Initialize the frequency arrays for the first window in 's'
    for (int i = 0; i < m; i++)
        arr1[p[i] - 'a']++, arr2[s[i] - 'a']++;

    // Check if the frequency arrays match for the first window
    if (arr1 == arr2)
        ans.push_back(0);

    // Iterate through the remaining windows in 's'
    for (int i = m; i < n; i++)
    {
        // Include the new character in the current window
        arr2[s[i] - 'a']++;

        // Remove the first character from the window
        arr2[s[i - m] - 'a']--;

        // Check if the frequency arrays match for the current window
        if (arr1 == arr2)
            ans.push_back(i - m + 1);
    }

    return ans;
}

// Main function
int main()
{
    // Example strings
    string s = "favavfvaf", p = "fav";

    // Find starting indices of anagrams
    vector<int> arr = FindAnagrams(s, p);

    // Display results
    if (arr.empty())
        cout << "There are No Anagrams of " << p << " in " << s << endl;
    else
    {
        cout << "Starting Indices of Anagrams are " << endl;
        for (auto &val : arr)
            cout << val << " ";
    }

    return 0;
}

Java Code

Find the Java code below to find all anagrams in a string:

import java.util.*;

class fav{
    // Function to find starting indices of anagrams of string 'p' in string 's'
    static ArrayList<Integer> FindAnagrams(String s, String p) {
        ArrayList<Integer> ans = new ArrayList<>();

        // Frequency arrays for characters in 'p' and the current window in 's'
        int[] arr1 = new int[26];
        int[] arr2 = new int[26];
        int n = s.length(), m = p.length();

        // If 'p' is longer than 's', no anagrams are possible
        if (m > n)
            return ans;

        // Initialize the frequency arrays for the first window in 's'
        for (int i = 0; i < m; i++) {
            arr1[p.charAt(i) - 'a']++;
            arr2[s.charAt(i) - 'a']++;
        }

        // Check if the frequency arrays match for the first window
        if (Arrays.equals(arr1, arr2))
            ans.add(0);

        // Iterate through the remaining windows in 's'
        for (int i = m; i < n; i++) {
            // Include the new character in the current window
            arr2[s.charAt(i) - 'a']++;

            // Remove the first character from the window
            arr2[s.charAt(i - m) - 'a']--;

            // Check if the frequency arrays match for the current window
            if (Arrays.equals(arr1, arr2))
                ans.add(i - m + 1);
        }

        return ans;
    }

    // Main function
    public static void main(String args[]) {
        // Example strings
        String s = "favavfvaf", p = "fav";

        // Find starting indices of anagrams
        ArrayList<Integer> arr = FindAnagrams(s, p);

        // Display results
        if (arr.isEmpty())
            System.out.println("There are No Anagrams of " + p + " in " + s);
        else {
            System.out.println("Starting Indices of Anagrams are ");
            for (int val : arr)
                System.out.print(val + " ");
        }
    }
}

Python Code

Check the python program to solve this problem:

def find_anagrams(s, p):
    ans = []
    # Frequency arrays
    arr1 = [0] * 26
    arr2 = [0] * 26
    n, m = len(s), len(p)

    if m > n:
        return ans

    # First window
    for i in range(m):
        arr1[ord(p[i]) - ord('a')] += 1
        arr2[ord(s[i]) - ord('a')] += 1

    if arr1 == arr2:
        ans.append(0)

    # Subsequent windows
    for i in range(m, n):
        arr2[ord(s[i]) - ord('a')] += 1
        arr2[ord(s[i - m]) - ord('a')] -= 1

        if arr1 == arr2:
            ans.append(i - m + 1)

    return ans

# Main function
def main():
    s = "favavfvaf"
    p = "fav"
    arr = find_anagrams(s, p)

    if not arr:
        print(f"There are No Anagrams of {p} in {s}")
    else:
        print("Starting Indices of Anagrams are:")
        print(*arr)

if __name__ == "__main__":
    main()

Output:

Starting Indices of Anagrams are 
0 3 5 6 

The Time Complexity to find all anagrams in a string using hashing and sliding windows is O((n-m+1)*26), because for loop iterates for “n – m + 1” times, representing the possible starting positions of substrings of length equal to string P within string S.

In each iteration, the frequency arrays of the current substring in string S and string P are compared. The Space Complexity of this optimized approach is O(1).

Here is the comparison of both approaches:

ApproachesTime ComplexitySpace ComplexityDetails 
Naive approach: SortingO(mlogm) + O( (n-m+1)*(m+mlogm+m) ) O(n*m) We take substrings from the window of size equal to the size of P and compare the sorted substrings with sorted P. If they are equal then they are anagrams.
Hashing + Sliding WindowO((n-m+1)*26) O(1)We take substrings from the window of size equal to the size of P and compare the hash table of characters substring with the hash table of P. If they are equal then they are anagrams.

Conclusion

In conclusion, the optimized Hashing + Sliding Window approach stands out as the most efficient solution for finding all anagrams in a string problem. This approach is recommended for larger datasets.

ShareTweetShareSendSend
Jatin Chanana

Jatin Chanana

I am Jatin, a final-year undergraduate student with a keen interest in the field of software development. I possess a strong academic background and a deep passion for Data Structures, Algorithms, and Web Development.

RelatedPosts

validate ip address

Validate IP Address Problem ( C++, JAVA, Python)

April 3, 2025
Shortest Palindrome Problem

Shortest Palindrome Problem ( C++, JAVA, Python)

April 4, 2025
Zigzag Conversion Problem

Zigzag Conversion Problem (C++, Java, Python)

April 4, 2025
Next Right Pointers In Each Node

Populating Next Right Pointers In Each Node (with code)

March 27, 2024
Coin Change II

Coin Change II Problem (C++, Java, Python)

April 7, 2025

About FavTutor

FavTutor is a trusted online tutoring service to connects students with expert tutors to provide guidance on Computer Science subjects like Java, Python, C, C++, SQL, Data Science, Statistics, etc.

Categories

  • AI News, Research & Latest Updates
  • Trending
  • Data Structures
  • Web Developement
  • Data Science

Important Subjects

  • Python Assignment Help
  • C++ Help
  • R Programming Help
  • Java Homework Help
  • Programming Help

Resources

  • About Us
  • Contact Us
  • Editorial Policy
  • Privacy Policy
  • Terms and Conditions

Website listed on Ecomswap. © Copyright 2025 All Rights Reserved.

No Result
View All Result
  • AI News
  • Data Structures
  • Web Developement
  • AI Code Generator
  • Student Help
  • Main Website

Website listed on Ecomswap. © Copyright 2025 All Rights Reserved.