LeetCode 242. Valid Anagram Solution Explained - Java

The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/...
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.d...
AlgoCademy - algocademy.com...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/...
Follow Me on X/Twitter - x.com/nickwhit...
Follow My Instagram - / nickwwhite
Other Social Media
----------------------------------------------
Discord - / discord
Twitch - / nickwhitettv
TikTok - / nickwhitetiktok
LinkedIn - / nicholas-w-white
Show Support
------------------------------------------------------------------------------
Patreon - / nick_white
PayPal - paypal.me/nick....
Become A Member - / @nickwhite
#coding #programming #softwareengineering

[@babumon5351]

Thanks. You are really good in algorithms..

[@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.

[@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.

[@Kitchen-Raccoon4572]

Thank you Mr. White always appreciated

[@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!

[@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.

[@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

[@maksymr.7191]

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

[@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.

[@ronyEdits110]

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

[@kathaigal27]

Sort them and check if they are equal or not

[@syed_4138]

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

[@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.

[@sachitdalwadi]

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

[@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.

[@sanchit537]

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

[@stoiandelev12345678]

interesting approach :)

[@chandanvishwakarma9203]

Thanks bro!

[@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.

[@Witch_Quiz]

thank

[@george_998]

perfect

[@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

[@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

[@lokanadhamc3827]

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

[@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