Isomorphic Strings (LeetCode 205) | Full solution using a HashMap | Easy to understand

[@jaxsyntax]

Nikhil, you are one of the only people that make these problems simple and easy to understand. I appreciate your efforts very much!

[@rishabhjain7651]

exactly

[@Maneeshce2007]

Really like the way of your explanation Nikhil , it encourages to solve DS problems which otherwise feels very frustrating.

[@vikashkatiyar1225]

u got a new subscriber , Thanks Nikhil for amazing quality content

[@manishbhardwaj4587]

best teacher, its hard to follow others even if they have same solution as you! Thankyou!!

[@XiaoFang-m8c]

Thank you so much for making these problems simple and easy to understand, your explanation is best.

[@sohrab6494]

Your explanations are great and you make them so much easier to understand. Can you also solve '605. Can Place Flowers'?

[@nikoo28]

thank you so much...sure I will add it to my pipeline of upcoming videos.

[@creative.shreative559]

God may bless this instructor ❤ Thank you sir🙌🏻🫶🏻

[@adveshdarvekar7733]

If you are coding in c++, you will need 2 hashmaps as you can't make sure the letter is not present in the key as well as the value.

[@abhishekshukla5747]

Right

[@rajmahto7946]

You are inspiration sir, keep similing

[@ashtonronald]

problem made extremely intuitive, gg!

[@dobermanbruce2397]

Really Appreciate your efforts

[@hoddybhaba6704]

Great explaination!

[@103_debopriyoghosh_cse_by6]

U are great , no idea why u are undeerrated

[@snehasaxena6551]

Found best teacher 🏆🏆

[@thebhagwabilla]

Awesome explanation sir

[@vilakshan.s]

As per leetcode looks like length of string can go till 5 * 10^4. So containsValue() can potentially end up doing nested looping with O(n) time complexity. Maybe we can improve this by having another reverse HashMap to improve the look up time. SpaceWise it will be 2X but I guess space is much cheaper than time :)

[@nikoo28]

Even if the string length is huge, you only have 256 different characters. This is almost constant time.

[@abhasranjandash249]

hi Nikhil,i think i have a solution using 2 hashMap where s.charAt(i) is key in one of the hashmap and t.charAt(i) in key for another hashmap.. in your solution containsValue() time complexity is O(n) which makes it little inefficient. rather if you will use 2 hashmap and use containskey() for which time complexity in O(1) as it use hashing. I ran both the solution in leetcode using one more hashmap is not increasing the memory drastically. but i am sure when the string length is very big, the solution provided in this video will take more time. class Solution { public boolean isIsomorphic(String s, String t) { if(s.length()!=t.length()){return false;} HashMap hmap= new HashMap(); HashMap hmap1= new HashMap(); for(int i=0;i

[@just_a_guy6985]

u dont need if condition at start in constraints its given that two strings are of same length

[@aryasharma69]

there can be a chance of different constraints. So that case is mandatory

[@bahubali1939]

Amazing sirr!! We love you..........

[@acethoughtless1596]

Very nice explanation !! Thank you!!

[@nikoo28]

Glad it was helpful!

[@ssss22144]

Nice explanation annaa

[@vinayaksharma7134]

nice explanation

[@parthapardhu3319]

Wow.. simply good sir

[@BACSShaileshShettar]

great explanation

[@mma-dost]

Java have a method to check the containsValue in the map, but cpp don't have that what should we do like creating another set for storing the values and then like check if the value contains in that something like this? This solved it but what about space complexity using map and set both.

[@nikoo28]

If you use std::unordered_map, which is implemented as a hash table, the average case time complexity for insertion, deletion, and search is O(1).

[@mma-dost]

thanks, bhaiya got it@@nikoo28

[@2550a]

why does chatGPT say that in this case time complexity is n^2? it says because you are in a for loop and each time you using containsValue(). Is that correct?

[@cricketkeeda3851]

bro at 9:15 timestamp you are wrong 'a' should be mapped with 'i' but you mapped it with 'd' , BTW good explanation

[@plutomessi21]

bhaiya this code passed 35/44 test cases class Solution { public boolean isIsomorphic(String s, String t) { ArrayList s1 = new ArrayList(); ArrayList s2 = new ArrayList(); int count = 1; for (int i = 1; i < s.length(); i++) { if (s.charAt(i) == s.charAt(i - 1)) { count++; } else { s1.add(count); count = 1; } } // s1.add(count); int count1 = 1; for (int i = 1; i < t.length(); i++) { if (t.charAt(i) == t.charAt(i - 1)) { count1++; } else { s2.add(count1); count1 = 1; } } s2.add(count1); return s1.equals(s2); } }

[@nikoo28]

have a look at the code in the video description. You will find a github link. That code passes all cases :)

[@plutomessi21]

@@nikoo28 thank you bhaiya

[@Atpataang]

You are fabbbbb

[@Harshu9669]

thanx brother

[@kevalkapadia8219]

is this code written in java or C++

[@vishalkushwaha6879]

Your code timecomplexity is O(n^2) and timecomplexity O(n)

[@lalanabiridi8358]

Hey nikhil i have a small doubt what happenns if we dont create a new variable mapped char but instead directly compare original with replacement i did that and out of 47 ..12 test cases failed

[@abhishekj2096]

This solution has runtime of 10ms and beats only 68%. Do you have a faster solution?

[@nikoo28]

don't go by these numbers you see on leetcode. If your solution is accepted, it is usually a good enough solution. The runtime usually depends on a lot of things: - the startup time of the VM - the language choice - the processor of the VM - the version of software stack

[@Isagi__000]

cool stuff.

[@hitheshpk6030]

Understood

[@filmonghebremariam8981]

Are "afa" and "dde" Isomorphic or not?

[@nikoo28]

they are not

[@mstinku9003]

easy way to solve this is l=len(set(zip(s,t)) a=len(s) b=len(t) return l==a==b: how easy it is using length

[@subee128]

Thanks

[@samiranroyy1700]

You said: why this shows this error please help.. class Solution { public boolean isIsomorphic(String s, String t) { int n = s.length(); int m = t.length(); if(n!=m) { return false; } Map sam = new HashMap(); for(int i=0;i

[@dupladupa-gl8lo]

u so sick dudeee

[@room5079]

why don't we do like this: finding charecter frequency arrays for both strings. sorting them ...and comparing the sorted values.

[@jst8922]

It is slower. n logn time.

[@ictfan-ly8gh]

It's will give wrong result if this is the test case Paper Tilte (it s not title) See here t and p will come two times in character freq array but we can see if p replaces t it will not give same word

[@hashcodez757]

some wondering O(n) kha se hai bhai ye? its not O(n^2) because :- The inner loop, despite being inside the for loop, checks only the characters in the map. Since the map can hold at most n elements (one for each character in the string), the overall complexity remains linear, i.e., O(n).

[@vishalkushwaha6879]

Bro you should learn java from the start the method he used contains value run in O(n) that's why this O(n2)

[@hashcodez757]

🤣 Brother I've spent days on this doubt. Trust me

[@AyushJain-m4u]

Will this code pass the test case s = "12" t = "\u0067\u0068"

[@nikoo28]

did you try it out?

[@dobermanbruce2397]

😍😍😍😍😍😍😍😍😍😍😍

[@ssss22144]

❤

[@ArunKumar-gx8iv]

public boolean isIsomorphic(String s, String t) { int n1 = s.length(); int n2 = t.length(); if (n1 != n2) { return false; } HashMap mapST = new HashMap(); HashMap mapTS = new HashMap(); for (int i = 0; i < n1; i++) { char c1 = s.charAt(i); char c2 = t.charAt(i); if (mapTS.containsKey(c1) && mapTS.get(c1) != c2) { return false; } if (mapST.containsKey(c2) && mapST.get(c2) != c1) { return false; } mapTS.put(c1, c2); mapST.put(c2, c1); } return true; }

[@delhidhamkhatushyam31]

how Paper and Title is isomorphic string you are teching wrong to students

[@Electrocode_gk]

very bad video

[@nikoo28]

can you please let me know which part was difficult to understand?

[@Electrocode_gk]

@@nikoo28 first description part it's self u confused

[@nikoo28]

which timestamp is confusing you? I added 4 different test cases to clear any confusion.

[@Electrocode_gk]

@@nikoo28 paper title how e r l e can be mapped e is common 4 case also true

[@nikoo28]

@@Electrocode_gk if "paper" is your start string, you are mapping E -> L, and R -> E but if "title" is your start string, then you map L -> E and E -> R You are mapping different characters. But in case 4, when you start from "kikp" you are mapping the same character K once to B and then to D. This is not allowed.

[@anveshsrivastava7786]

won't the time complexity be O(N^2) as the the containsValue() method goes through all the key value pairs in a hashmap? can someone please clarify

[@sidharthan3349]

yes same doubt

[@sidharthan3349]

@nikoo28 can you please reply

[@sachinboreoffl]

In the hashmap, at max u can have 256 characters so it's a constant time

[@vivekkumaryadav9862]

def isIsomorphic(self, s, t): map1 = [] map2 = [] for idx in s: map1.append(s.index(idx)) for idx in t: map2.append(t.index(idx)) if map1 == map2: return True return False

[@Krixnbhakt]

I'm not able to understand the second else condition - else{ char mappedCharacter = charMappingMap.get(original); if (mappedCharacter != replacement)return false;}

[@anilkumarsingh7141]

Just think opposite like s1 = "kikp" and s2 = "badc" . I hope you got it