{"id":749,"date":"2020-06-10T11:45:49","date_gmt":"2020-06-10T11:45:49","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=749"},"modified":"2022-04-06T08:28:12","modified_gmt":"2022-04-06T08:28:12","slug":"anagram-or-not","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/anagram-or-not\/","title":{"rendered":"Anagram or Not"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Strings, Hashing<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Easy<\/p>\n<\/blockquote>\n

Problem Statement (Simplified):<\/h3>\n
\n

Check if string B<\/strong> can be achieved by A<\/strong> by rearranging letters of A<\/strong>. If yes print Yes<\/strong> else No<\/strong>;<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Test Case<\/h4>\n
Input:\n1\nprep\nperp\n\nOutput:\nYES\n\nExplanation:\nWe can achieve string B from string A if we rearrange 'r', 'e' and 'p' in string A. All possible arrangements for 'prep' are :\n\nprep\nrpep\neprp\nperp\nrepp\nerpp\npper\neppr\npepr\nrppe\nprpe\nppre\n\nAs we can see 'pepr' is in these arrangements. So they are anagram to each other.<\/code><\/pre>\n
Solving Approach :<\/h3>\n
Bruteforce Approach:<\/strong><\/p>\n
    \n
  1. \n
    It can be solved by rearranging all letters of A<\/code> and then checking all permutations, if any permutation is the same as B<\/code>, then print Yes<\/code>, else if no permutation is same, we print No<\/code>. But this is not an efficient solution as it will take O(n!) time complexity to check all permutations where n is the length of the string.<\/p>\n<\/li>\n
  2. \n
    Can you see, the above approach takes longer times for longer strings, but this can be solved more efficiently. Can you guess? Let’s see a more efficient approach.<\/p>\n<\/li>\n<\/ol>\n
    Efficient Approach:<\/strong><\/p>\n
      \n
    • As we saw in the last approach, it was very inefficient, we can use Hashing<\/em><\/strong> to solve this problem more efficiently.<\/li>\n
    • Hashing<\/strong>: This method uses a hash table that stores each character of alphabets as an index and corresponding value related to character, in our case it stores the number of times a character appears in a string.<\/li>\n<\/ul>\n
        \n
      1. For two strings to be an anagram, they need to follow two conditions that are :\n
          \n
        • They must be of equal length.<\/li>\n
        • They must have the same characters appearing the same number of times in any order.<\/li>\n<\/ul>\n<\/li>\n
        • We can check for condition 2 which provides a more efficient solution to us. <\/li>\n
        • To keep count of character’s appearance, we use a hash table of size 26, where index 0 to 26 refer to letters in alphabets i.e. a<\/code> to z<\/code>.<\/li>\n
        • To get the index value of any character S[i]<\/code> we subtract a<\/code> from it, hence the resultant provides a valid index.<\/li>\n
        • When we decrease a<\/code> from any character, it substracts 97(a’s ASCII Value<\/strong>) from it’s ASCII Value giving it’s valued between 0 and 26, for example, b<\/code> has ASCII value 97, when we subtract a<\/code> from it, it results in 1. Hence, index 1 will store the number of appearances of b<\/code>.<\/li>\n
        • So we count appearances of the character in both string and match them if all are found the same, that means they’re anagram, else they are not.<\/li>\n<\/ol>\n
          Example<\/h3>\n
          \n
            \n
          • \n
            Lets assume string A<\/code> be prep and string B<\/code> be pepr.<\/p>\n<\/li>\n
          • \n
            Initially our hash table h<\/code> have 0 at all places.<\/p>\n<\/li>\n
          • \n
            For every character we read, it’s the corresponding index in the hash table can be achieved by using the following formula :<\/p>\n<\/li>\n
          • \n
            index = ASCII(c) – ASCII(‘a’) where c is current character.<\/p>\n<\/li>\n
          • \n
            For example, for character p it’s corresponding index will be ASCII(‘p’)-ASCII(‘a’) i.e. 112 – 97 =  15. So at every appearance of character p, we’ll increase value at index 15 by 1.<\/p>\n<\/li>\n
          • \n
            So after counting, our hash tables (with corresponding index and character) becomes,<\/p>\n<\/li>\n<\/ul>\n<\/blockquote>\n
            Graphic-1 Here<\/em><\/strong><\/p>\n
            \n
              \n
            • \n
              where hA stores appearances of characters in string A, while hB stores appearances of characters in string B.<\/p>\n<\/li>\n
            • \n
              After we have counted all appearances in string A<\/code> and string B<\/code>, we check if all characters appear the same number of time or not.<\/p>\n<\/li>\n
            • \n
              If all characters appear same number of time in both strings, both strings are Anagram else they are not.<\/p>\n<\/li>\n
            • \n
              As we can see in the above figure, all characters have same values at same indexes in hash tables, hence they’re Anagram.<\/p>\n<\/li>\n<\/ul>\n<\/blockquote>\n
              Solutions<\/h3>\n
              \t\t\t\t\t\t