{"id":1535,"date":"2024-01-28T13:00:00","date_gmt":"2024-01-28T13:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=1535"},"modified":"2024-01-30T06:38:37","modified_gmt":"2024-01-30T06:38:37","slug":"find-all-anagrams-string","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/find-all-anagrams-string\/","title":{"rendered":"Find all Anagrams in a String (C++, Java, Python)"},"content":{"rendered":"\n

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.<\/p>\n\n\n\n

Find all Anagrams in a String Problem<\/strong><\/h2>\n\n\n\n

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.”<\/p>\n\n\n\n

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.<\/strong><\/p>\n\n\n\n

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.<\/p>\n\n\n\n

Let us discuss it with an example:<\/p>\n\n\n\n

Input:<\/strong><\/p>\n\n\n\n

S = \"favavfvaf\" \nP = \"fav\"<\/code><\/pre>\n\n\n\n
Output:<\/strong><\/p>\n\n\n\n
[0, 3, 5, 6]<\/code><\/pre>\n\n\n\n
Naive Approach: Using Sorting <\/strong><\/h2>\n\n\n\n
In this approach, we will use the concept of sorting the string.\u00a0Let us understand it better with an example:<\/p>\n\n\n\n
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.<\/p>\n\n\n\n
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.<\/strong>\u00a0<\/p>\n\n\n\n
Firstly we will sort P and after sorting P becomes \u201cafv\u201d Then we will iterate over S with a Window equal to P\u2019s length.<\/p>\n\n\n\n
After taking that particular substring from the current window (let\u2019s 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.<\/p>\n\n\n\n
Sorted P<\/strong> = \u201cafv\u201d<\/p>\n\n\n\n
Window size<\/strong> = 3<\/p>\n\n\n\n
Current window substring<\/strong> = \u201cfav\u201d<\/p>\n\n\n\n
Sorted substring<\/strong> = \u201cafv\u201d<\/p>\n\n\n
\n
\"Window<\/figure>\n<\/div>\n\n\n
Similarly, we will take all windows of size 3<\/p>\n\n\n\n
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.<\/p>\n\n\n\n
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)).<\/p>\n\n\n\n
The Space Complexity of this approach is O(m) because of the sorted string P and the temporary substring (temp) created in each iteration.<\/p>\n\n\n\n
Optimized Approach: Hashing + Sliding Window<\/strong><\/h2>\n\n\n\n
The best way to find all anagrams in a string is by using hashing with sliding windows.<\/strong> We will use hashing<\/a> and sliding windows<\/a> 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.\u00a0<\/p>\n\n\n\n
Below is the step-by-step guide to using hashing to find all anagrams:<\/p>\n\n\n\n
    \n
  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.<\/li>\n\n\n\n
  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. <\/li>\n\n\n\n
  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.<\/li>\n<\/ol>\n\n\n
    \n
    \"Example\"\/<\/figure>\n<\/div>\n\n\n
    Window size = Size of P = 3
    <\/p>\n\n\n
    \n
    \"Hash<\/figure>\n<\/div>\n\n
    \n
    \"Hash<\/figure>\n<\/div>\n\n\n
    The hash table of both the current window substring and the hash table of string P are the same.<\/p>\n\n\n\n
    Hence both are anagrams.<\/p>\n\n\n\n
    Similarly, take all windows of size 3.<\/p>\n\n\n\n
    C++ Code<\/strong><\/h3>\n\n\n\n
    Here is the implementation in C++:<\/p>\n\n\n\n
    #include <bits\/stdc++.h>\nusing namespace std;\n\n\/\/ Function to find starting indices of anagrams of string 'p' in string 's'\nvector<int> FindAnagrams(string &s, string &p)\n{\n    \/\/ Vector to store the starting indices of anagrams\n    vector<int> ans;\n\n    \/\/ Frequency arrays for characters in 'p' and the current window in 's'\n    vector<int> arr1(26, 0), arr2(26, 0);\n\n    \/\/ Lengths of strings 's' and 'p'\n    int n = s.length(), m = p.length();\n\n    \/\/ If 'p' is longer than 's', no anagrams are possible\n    if (m > n)\n        return ans;\n\n    \/\/ Initialize the frequency arrays for the first window in 's'\n    for (int i = 0; i < m; i++)\n        arr1[p[i] - 'a']++, arr2[s[i] - 'a']++;\n\n    \/\/ Check if the frequency arrays match for the first window\n    if (arr1 == arr2)\n        ans.push_back(0);\n\n    \/\/ Iterate through the remaining windows in 's'\n    for (int i = m; i < n; i++)\n    {\n        \/\/ Include the new character in the current window\n        arr2[s[i] - 'a']++;\n\n        \/\/ Remove the first character from the window\n        arr2[s[i - m] - 'a']--;\n\n        \/\/ Check if the frequency arrays match for the current window\n        if (arr1 == arr2)\n            ans.push_back(i - m + 1);\n    }\n\n    return ans;\n}\n\n\/\/ Main function\nint main()\n{\n    \/\/ Example strings\n    string s = "favavfvaf", p = "fav";\n\n    \/\/ Find starting indices of anagrams\n    vector<int> arr = FindAnagrams(s, p);\n\n    \/\/ Display results\n    if (arr.empty())\n        cout << "There are No Anagrams of " << p << " in " << s << endl;\n    else\n    {\n        cout << "Starting Indices of Anagrams are " << endl;\n        for (auto &val : arr)\n            cout << val << " ";\n    }\n\n    return 0;\n}<\/pre><\/div>\n\n\n\n
    Java Code<\/strong><\/h3>\n\n\n\n
    Find the Java code below to find all anagrams in a string:<\/p>\n\n\n\n
    import java.util.*;\n\nclass fav{\n    \/\/ Function to find starting indices of anagrams of string 'p' in string 's'\n    static ArrayList<Integer> FindAnagrams(String s, String p) {\n        ArrayList<Integer> ans = new ArrayList<>();\n\n        \/\/ Frequency arrays for characters in 'p' and the current window in 's'\n        int[] arr1 = new int[26];\n        int[] arr2 = new int[26];\n        int n = s.length(), m = p.length();\n\n        \/\/ If 'p' is longer than 's', no anagrams are possible\n        if (m > n)\n            return ans;\n\n        \/\/ Initialize the frequency arrays for the first window in 's'\n        for (int i = 0; i < m; i++) {\n            arr1[p.charAt(i) - 'a']++;\n            arr2[s.charAt(i) - 'a']++;\n        }\n\n        \/\/ Check if the frequency arrays match for the first window\n        if (Arrays.equals(arr1, arr2))\n            ans.add(0);\n\n        \/\/ Iterate through the remaining windows in 's'\n        for (int i = m; i < n; i++) {\n            \/\/ Include the new character in the current window\n            arr2[s.charAt(i) - 'a']++;\n\n            \/\/ Remove the first character from the window\n            arr2[s.charAt(i - m) - 'a']--;\n\n            \/\/ Check if the frequency arrays match for the current window\n            if (Arrays.equals(arr1, arr2))\n                ans.add(i - m + 1);\n        }\n\n        return ans;\n    }\n\n    \/\/ Main function\n    public static void main(String args[]) {\n        \/\/ Example strings\n        String s = "favavfvaf", p = "fav";\n\n        \/\/ Find starting indices of anagrams\n        ArrayList<Integer> arr = FindAnagrams(s, p);\n\n        \/\/ Display results\n        if (arr.isEmpty())\n            System.out.println("There are No Anagrams of " + p + " in " + s);\n        else {\n            System.out.println("Starting Indices of Anagrams are ");\n            for (int val : arr)\n                System.out.print(val + " ");\n        }\n    }\n}<\/pre><\/div>\n\n\n\n
    Python Code<\/strong><\/h3>\n\n\n\n
    Check the python program to solve this problem:<\/p>\n\n\n\n
    def find_anagrams(s, p):\n    ans = []\n    # Frequency arrays\n    arr1 = [0] * 26\n    arr2 = [0] * 26\n    n, m = len(s), len(p)\n\n    if m > n:\n        return ans\n\n    # First window\n    for i in range(m):\n        arr1[ord(p[i]) - ord('a')] += 1\n        arr2[ord(s[i]) - ord('a')] += 1\n\n    if arr1 == arr2:\n        ans.append(0)\n\n    # Subsequent windows\n    for i in range(m, n):\n        arr2[ord(s[i]) - ord('a')] += 1\n        arr2[ord(s[i - m]) - ord('a')] -= 1\n\n        if arr1 == arr2:\n            ans.append(i - m + 1)\n\n    return ans\n\n# Main function\ndef main():\n    s = "favavfvaf"\n    p = "fav"\n    arr = find_anagrams(s, p)\n\n    if not arr:\n        print(f"There are No Anagrams of {p} in {s}")\n    else:\n        print("Starting Indices of Anagrams are:")\n        print(*arr)\n\nif __name__ == "__main__":\n    main()<\/pre><\/div>\n\n\n\n
    Output:<\/strong><\/p>\n\n\n\n
    Starting Indices of Anagrams are \n0 3 5 6 <\/code><\/pre>\n\n\n\n
    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. <\/p>\n\n\n\n
    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).<\/p>\n\n\n\n
    Here is the comparison of both approaches:<\/p>\n\n\n\n
    Approaches<\/strong><\/td>Time Complexity<\/strong><\/td>Space Complexity<\/strong><\/td>Details\u00a0<\/strong><\/td><\/tr>
    Naive approach: Sorting<\/td>O(mlogm) + O( (n-m+1)*(m+mlogm+m) ) <\/td>O(n*m) <\/td>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.<\/td><\/tr>
    Hashing + Sliding Window<\/td>O((n-m+1)*26) <\/td>O(1)<\/td>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.<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
    Conclusion<\/strong><\/h2>\n\n\n\n
    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.<\/p>\n","protected":false},"excerpt":{"rendered":"
    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 […]<\/p>\n","protected":false},"author":12,"featured_media":1537,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[14,15],"class_list":["post-1535","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dsa","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1535","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/12"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=1535"}],"version-history":[{"count":4,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1535\/revisions"}],"predecessor-version":[{"id":1588,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1535\/revisions\/1588"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/1537"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=1535"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=1535"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=1535"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}