{"id":1094,"date":"2023-12-17T17:00:00","date_gmt":"2023-12-17T17:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=1094"},"modified":"2023-12-20T09:33:45","modified_gmt":"2023-12-20T09:33:45","slug":"valid-anagram","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/valid-anagram\/","title":{"rendered":"Valid Anagram: Check if Two Strings are Anagram of Each Other"},"content":{"rendered":"\n<p>Anagrams are an interesting concept in the realm of programming that most new techies feel a little confused about. In this article, our goal is to explore one such leet code problem called &#8216;Valid Anagram&#8217; where we have to check whether two strings are Anagrams of each other with a proper solution.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>What is a Valid Anagram Problem?<\/strong><\/h2>\n\n\n\n<p>An anagram is a word formed by rearranging the letters of another word, using all the original letters exactly once.<\/p>\n\n\n\n<p><strong>In the Valid Anagram problem, we are given two strings and we have to check if the two strings contain the same characters, regardless of their order.<\/strong><\/p>\n\n\n\n<p>Let us understand it with a couple of examples below:<\/p>\n\n\n\n<p class=\"has-black-color has-text-color has-background\" style=\"background-color:#fedcba\"><strong>Input<\/strong>: s = &#8220;cab&#8221;, t = &#8220;abc&#8221;<br><strong>Output<\/strong>: True<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/-BfdIQt28bXeOpVrA3BdI_pkg297eN-HIB82Z6Wun2gqSwNvXccFl-WnAqFOjKVmc-coAB30uf5R7I-Lh3h6VUyIJwFgMjFY8ALZC9HZIIaANSy4EFo7PhcHzMasNqLcp8nP88b-k1Z7_rXH4jTOkeg\" alt=\"Example of valid anagram\"\/><\/figure>\n\n\n\n<p>Both the strings contain \u2018a\u2019, \u2018b\u2019, and \u2018c\u2019 each.<\/p>\n\n\n\n<p class=\"has-black-color has-text-color has-background\" style=\"background-color:#fedcba\"><strong>Input<\/strong>: s = &#8220;rat&#8221;, t = &#8220;car&#8221;<br><strong>Output<\/strong>: false<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"419\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-15-1024x419.png\" alt=\"Example of invalid anagram\" class=\"wp-image-1095\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-15-1024x419.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-15-300x123.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-15-768x314.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-15-750x307.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-15-1140x467.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-15.png 1280w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<p>The first string contains \u2018r\u2019, \u2018a&#8217;, and \u2018t\u2019, and the second string contains \u2018c\u2019, \u2018a\u2019, and \u2018r\u2019.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Naive Approach: Sorting<\/strong><\/h2>\n\n\n\n<p>In this approach we will compare both strings after sorting them, if they are not equal at any point then we will return false otherwise they are anagrams of each other.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter is-resized\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/zML9443mTIU73zwU36y2qvtrADKWEHH9sH9rFDM9Moo0v6qAOQzlFPrZXWpSh5Fo8KwNVhA7gdKFzJE8cLE4UVc0SWf3-Kx7gCORhsBAbpWoPmyrznEg-tjRye31CXXCHLSQDbrozan6tjgKxSTjoKY\" alt=\"Sorting Approach\" style=\"aspect-ratio:2.826923076923077;width:504px;height:auto\"\/><\/figure>\n<\/div>\n\n\n<p><strong>Steps used in this approach<\/strong>:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Firstly we will check the lengths of two input strings, the lengths of two strings should be equal to further check if they are valid anagrams.<\/li>\n\n\n\n<li>Now we will sort both strings and run a loop to check each character of the first string with each character of the second string.<\/li>\n\n\n\n<li>If we find a different character in a sorted string then we will return a false<\/li>\n\n\n\n<li>If each character of both strings matches. Then they are valid anagrams.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Complexity Analysis<\/strong><\/h3>\n\n\n\n<p>The <strong>time complexity of this approach is O(n * logn), <\/strong>&nbsp;as in this we are running our loop for n times and <strong>log n <\/strong>for sorting of strings<br>The <strong>space complexity is O(1) <\/strong>as we are not using any extra space.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Optimized Approach: Using Hashing<\/strong><\/h2>\n\n\n\n<p>In the <a href=\"https:\/\/favtutor.com\/blogs\/hashing-in-data-structure\" data-type=\"link\" data-id=\"https:\/\/favtutor.com\/blogs\/hashing-in-data-structure\">hashing approach<\/a>, we will use a hashmap data structure to check if two strings are valid anagrams. Here are all the steps involved:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Firstly we will check the lengths of two input strings, the lengths of two strings should be equal to further check if they are valid anagrams.<\/li>\n\n\n\n<li>Now we will create a hashmap mp to store the frequency of each character in the first string. The loop iterates through each character in the first string and increments its count in the map.<\/li>\n\n\n\n<li>Now we will run another loop that iterates through each character in the second string decreasing the count of each character in the map.<\/li>\n\n\n\n<li>If the second string has a character that is not present in the first string or has more occurrences than in the first string, it will result in a negative count.<\/li>\n\n\n\n<li>A final loop iterates through the map, checking if any character has a non-zero count<\/li>\n\n\n\n<li>If any character has a count other than zero, it means the frequencies in the first string and second string are not the same, indicating that the strings are not anagrams.<\/li>\n\n\n\n<li>If the loop completes without finding such a character, the function returns true, indicating that the strings are valid anagrams.<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>C++ Code<\/strong><\/h3>\n\n\n\n<p>Let&#8217;s implement all the above steps in C++:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-c++src&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;C++&quot;,&quot;modeName&quot;:&quot;cpp&quot;}\">#include &lt;bits\/stdc++.h&gt;\nusing namespace std;\n\nbool areAnagrams(const string&amp; a, const string&amp; b) {\n    \/\/ Check if the lengths of the strings are different\n    if (a.length() != b.length()) {\n        return false;\n    }\n\n    \/\/ Create a map to store the frequency of each character in the first string\n    unordered_map&lt;char, int&gt; mp;\n    for (int i = 0; i &lt; a.length(); i++) {\n        mp[a[i]]++;\n    }\n\n    \/\/ Adjust the frequency counts based on the second string\n    for (int i = 0; i &lt; b.length(); i++) {\n        mp[b[i]]--;\n    }\n\n    \/\/ Check if any character has a non-zero count, indicating the strings are not anagrams\n    for (const auto&amp; it : mp) {\n        if (it.second != 0) {\n            return false;\n        }\n    }\n\n    \/\/ If the loop completes without returning, the strings are anagrams\n    return true;\n}\n\nint main() {\n    string string1 = &quot;cab&quot;;\n    string string2 = &quot;abc&quot;;\n\n    if (areAnagrams(string1, string2)) {\n        cout &lt;&lt; &quot;\\&quot;&quot; &lt;&lt; string1 &lt;&lt; &quot;\\&quot; and \\&quot;&quot; &lt;&lt; string2 &lt;&lt; &quot;\\&quot; are anagrams!&quot; &lt;&lt; endl;\n    } else {\n        cout &lt;&lt; &quot;\\&quot;&quot; &lt;&lt; string1 &lt;&lt; &quot;\\&quot; and \\&quot;&quot; &lt;&lt; string2 &lt;&lt; &quot;\\&quot; are not anagrams.&quot; &lt;&lt; endl;\n    }\n\n    return 0;\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Python Code<\/strong><\/h3>\n\n\n\n<p>Let&#8217;s implement the hashing approach in Python:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;python&quot;,&quot;mime&quot;:&quot;text\/x-python&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Python&quot;,&quot;modeName&quot;:&quot;python&quot;}\">def are_anagrams(a, b):\n    # Check if the lengths of the strings are different\n    if len(a) != len(b):\n        return False\n\n    # Create a dictionary to store the frequency of each character in the first string\n    char_count = {}\n    for char in a:\n        char_count[char] = char_count.get(char, 0) + 1\n\n    # Adjust the frequency counts based on the second string\n    for char in b:\n        if char not in char_count:\n            return False\n        char_count[char] -= 1\n\n    # Check if any character has a non-zero count, indicating the strings are not anagrams\n    for count in char_count.values():\n        if count != 0:\n            return False\n\n    # If the loop completes without returning, the strings are anagrams\n    return True\n\n# Example usage\nstring1 = &quot;cab&quot;\nstring2 = &quot;abc&quot;\n\nif are_anagrams(string1, string2):\n    print(f'&quot;{string1}&quot; and &quot;{string2}&quot; are anagrams!')\nelse:\n    print(f'&quot;{string1}&quot; and &quot;{string2}&quot; are not anagrams.')<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Java Code<\/strong><\/h3>\n\n\n\n<p>Here is the Java program as well:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-java&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Java&quot;,&quot;modeName&quot;:&quot;java&quot;}\">import java.util.HashMap;\nimport java.util.Map;\n\npublic class AnagramChecker {\n\n    public static boolean areAnagrams(String a, String b) {\n        \/\/ Check if the lengths of the strings are different\n        if (a.length() != b.length()) {\n            return false;\n        }\n\n        \/\/ Create a map to store the frequency of each character in the first string\n        Map&lt;Character, Integer&gt; charCount = new HashMap&lt;&gt;();\n        for (int i = 0; i &lt; a.length(); i++) {\n            char c = a.charAt(i);\n            charCount.put(c, charCount.getOrDefault(c, 0) + 1);\n        }\n\n        \/\/ Adjust the frequency counts based on the second string\n        for (int i = 0; i &lt; b.length(); i++) {\n            char c = b.charAt(i);\n            if (!charCount.containsKey(c)) {\n                return false;\n            }\n            charCount.put(c, charCount.get(c) - 1);\n        }\n\n        \/\/ Check if any character has a non-zero count, indicating the strings are not anagrams\n        for (int count : charCount.values()) {\n            if (count != 0) {\n                return false;\n            }\n        }\n\n        \/\/ If the loop completes without returning, the strings are anagrams\n        return true;\n    }\n\n    public static void main(String[] args) {\n        String string1 = &quot;cab&quot;;\n        String string2 = &quot;abc&quot;;\n\n        if (areAnagrams(string1, string2)) {\n            System.out.println(&quot;\\&quot;&quot; + string1 + &quot;\\&quot; and \\&quot;&quot; + string2 + &quot;\\&quot; are anagrams!&quot;);\n        } else {\n            System.out.println(&quot;\\&quot;&quot; + string1 + &quot;\\&quot; and \\&quot;&quot; + string2 + &quot;\\&quot; are not anagrams.&quot;);\n        }\n    }\n}<\/pre><\/div>\n\n\n\n<p><strong>Output:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code has-black-color has-text-color has-background\" style=\"background-color:#fedcba\"><code>\"cab\" and \"abc\" are anagrams!<\/code><\/pre>\n\n\n\n<p>The Time complexity is O(n) for the hashing approach to check if two strings are anagrams of each other, where n is the length of the input strings. The loop iterating through the unordered_map contributes a constant factor based on the number of distinct characters<\/p>\n\n\n\n<p>The space complexity is O(c), where c is the number of distinct characters in both strings. In the worst case, this is O(26) for lowercase English letters.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Analysis of Both the Approaches<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>Approaches<\/td><td>Time complexity<\/td><td>Space complexity<\/td><td>Details<\/td><\/tr><tr><td>Sorting&nbsp;Approach<\/td><td>O(n * logn)<\/td><td>O(1)<\/td><td>In this we have used a loop that iterates for the length of the string&nbsp;<\/td><\/tr><tr><td>Hashing&nbsp;Approach<\/td><td>O(n)<\/td><td>O(c)<\/td><td>In this loop iterates through the unordered_map contributes a constant factor based on the number of distinct characters&nbsp;<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Conclusion<\/strong><\/h2>\n\n\n\n<p>In conclusion, we found a perfect solution to the famous Valid Anagram <a href=\"https:\/\/leetcode.com\/problems\/valid-anagram\/\" target=\"_blank\" data-type=\"link\" data-id=\"https:\/\/leetcode.com\/problems\/valid-anagram\/\" rel=\"noreferrer noopener nofollow\">leetcode problem<\/a> using hashing. We also provided the complete programs in C++, Python, and Java, along with the time and space complexities.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Anagrams are an interesting concept in the realm of programming that most new techies feel a little confused about. In this article, our goal is to explore one such leet code problem called &#8216;Valid Anagram&#8217; where we have to check whether two strings are Anagrams of each other with a proper solution. What is a [&hellip;]<\/p>\n","protected":false},"author":12,"featured_media":1098,"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-1094","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\/1094","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=1094"}],"version-history":[{"count":4,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1094\/revisions"}],"predecessor-version":[{"id":1109,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1094\/revisions\/1109"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/1098"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=1094"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=1094"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=1094"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}