LeetCode 242. Valid Anagram Solution Explained - Java

[@sheriffcrandy]

I understand that char 'a' is the ACSII symbol whose value is 97, but how does this for (int i = 0; i < s.length(); i++) { characterCount[s.charAt(i) - 'a']++; characterCount[t.charAt(i) - 'a']--; } check for anagrams? Why can't I use any other ACSII symbol char like 'b' or 'c'?

[@Gazeld]

In the first line, we store in char_count array the number of occurences of each letter encountered in string s : each time we encounter a 'a', the content of char_count[0] is increased. In the second line, we do almost the same for string t, but decreasing the same element in the array. This way if the number of occurences of a letter in t is the same as in s, the corresponding count in char_count[] must be 0. And if this is true for all the letters (all the elements of the array are 0), that means we have an anagram, because neither of s or t has more occurences of a letter. "Why can't I use any other ACSII symbol char like 'b' or 'c'?" : 'a' here is taken as the basis, since this is the first letter in the alphabet, so taking the ascii value of any letter and substracting the ascii code of 'a' from it will give us 0-25, the perfect indexes for our array to store our letter count of occurrences.

[@tamilchad6165]

@@Gazeld each time we encounter a 'a', the content of char_count[0] is increased. which means char_count[1] and after another encounter it becomes char_counter[2]??

[@ruben5233]

I know this is old but here it goes: If we look at the ASCII table, the decimal value for 'a' is 97, 'b' 98 and so on until 'z' which is 122. If we were to store the characters count with these indexes, we would need an int[] array of size 123 and we would not be using indexes 0 to 96. So by subtracting 97('a') to each character's decimal value, we ensure we only use indexes 0 to 25 (thus an int array of size 26). 'a' = 97 - 97 = 0 'b' = 98 - 97 = 1 . . 'z' = 122 - 97 = 25 Now, at these positions, we increment by one how many times we see a character for S and decrement its value every time we see the character in T. In the end if they are anagrams we should have 0 at every position. If we have -1, -2, 1, 2, 3 or any other number it means we have more occurrences of a letter in either of the Strings and they are not anagrams.

[@babumon5351]

Thanks. You are really good in algorithms..

[@Kitchen-Raccoon4572]

Thank you Mr. White always appreciated

[@saiavinashduddupudi8975]

What is the space complexity here?

[@danw6922]

I think the space complexity is O(1), because although it uses an int array, but it's fix sized (26 integer).This int array does not change its size when string grows.

[@mosbahhoucemeddine1147]

@@danw6922 no i think O(n) because no matter is the size ..if the size is 2 it is also n

[@Gazeld]

@@mosbahhoucemeddine1147 No, it would be O(n) if the size was depending on the size of the strings ; here the size of the array does not depend on anything.

[@samj9822]

Can we create StringBuilder for t and start removing one (only) character for each character in s. If StringBuilder is left with zero element then return true.

[@philbowden]

Starting your video with "this is one of the easiest problems," tends to be a bit of a turn off. If the problem was easy for your viewers we would not be viewing your tutorial.

[@oingomoingo7411]

haha i also thought that

[@stepbystepcoding4113]

@@oingomoingo7411 me too

[@carguy-xv2cl]

Exactly, sounds so arrogant.

[@vivekmishra641]

True

[@Gazeld]

@@carguy-xv2cl It's not, and you know it. It simply means there are far more difficult problems.

[@shiyangnie6738]

Still confused about the char_count[s.charAt(i)-'a'] and the char_count[t.charAt(i)-'a'];

[@akshatpahwa534]

Read about ASCII values.

[@sheriffcrandy]

@@maxlievikoff2162 I still don't get it. how does char_count[s.charAt(i)-'a']++; and char_count[t.charAt(i)-'a']--; check for anagrams?

[@Gazeld]

@@sheriffcrandy In the first line, we store in char_count array the number of occurences of each letter encountered in string s : each time we encounter a 'a', the content of char_count[0] is increased. In the second line, we do almost the same for string t, but *decreasing* the same element in the array. This way if the number of occurences of a letter in t is the same as in s, the corresponding count in char_count[] must be 0. And if this is true for all the letters (all the elements of the array are 0), that means we have an anagram, because neither of s or t has more occurences of a letter.

[@billynader0]

Hi, when I saw the solution, at first I did not get it until I watched your solution I solved it with HasMap run time and memory was too high

[@mohamedsayed8697]

Same

[@ritchievales]

I solved it by using two hashmaps and three for loops.... feeling so stupid after seeing this solution 😢

[@robertcole3260]

I did the same exact thing lol.

[@isaacli8376]

very clear and simple solution, thank you!

[@maksymr.7191]

Thank you, my friend. That's what I need now to survive.

[@ronyEdits110]

the code showing wrong answer when you check for the input rat and car

[@debdijmazumder7182]

would a hashmap be more or less efficient?

[@Hrit]

I used a HashMap too, it would be same, either way it is going to take O(1) for incrementing and decrementing the count. Apart from that, if you do it in 2 traversals (i.e one traversal for incrementing and decrementing and other one for checking) - time complexity is O(n).

[@ericsodt]

("Hello", "hello") leads to indexOutOfBoundsException. The capital 'H' is the issue here.

[@mohamedsayed8697]

Check leetcode description it says the input string is lowercase only, so this solution is valid for lowercase cases only.

[@kathaigal27]

Sort them and check if they are equal or not

[@syed_4138]

Well one of the easiest solution i came across thank you.

[@sachitdalwadi]

Very help full I wish I could support you more than I can

[@stoiandelev12345678]

interesting approach :)

[@jacobodoyo2793]

just learned the code

[@zihaoyan4741]

I tried using Hashmap but got me 24ms, time complexity I beleive was O(m+n). that is the best I could do if this is a interview question...LoL. Never would have come up with this solution.

[@sanchit537]

Good solution bad explanation. Where's my Indian guy explaining iteration at?

[@Impromptu21]

Why dont sort both strings and compare if they both r same ..return true if it is else false

[@woodendscott]

If you sort best case time complexity is O(n log n). The solution provided here is O(n)

[@vishwaskhurana1217]

@@Godsu0417 hahahahah

[@chandanvishwakarma9203]

Thanks bro!

[@patrakarpopatlaltoofanexpr3258]

"MOST EASIEST SOLUTION" class Solution { public boolean isAnagram(String s, String t) { if(s.length()!=t.length()){ return false; } char[] st_s=s.toCharArray(); char[] st_t=t.toCharArray(); Arrays.sort(st_s); Arrays.sort(st_t); for(int i=0;i

[@Donkle365]

but it's more complex than the solution of the video

[@karanaa1093]

@@Donkle365 no not at all. Its just checking if the arrays from each string are equal.

[@karthikprabhu_career]

Thank you Popatlal !! Your code is pretty easy to understand

[@patrakarpopatlaltoofanexpr3258]

@@karthikprabhu_career Thanks Karthik, Long code ko kaho cancel, cancel, cancel !

[@mosbahhoucemeddine1147]

blh bara nayek

[@lokanadhamc3827]

i think you should have submit the code to see all testcase passed or not

[@Witch_Quiz]

thank

[@george_998]

perfect

[@amerelsayed]

java.lang.ArrayIndexOutOfBoundsException: Index 13 out of bounds for length 1 at line 12, Solution.isAnagram at line 54, __DriverSolution__.__helper__ at line 87, __Driver__.main this exception is happen

[@jamsranjavodgerel803]

Thanks for the video