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

Chapters:
00:00 - Intro
00:41 - Problem Statement and Description
03:37 - Brute Force has limitations
06:03 - Efficient Solution
09:39 - Dry-run of Code
13:01 - Final Thoughts

📚 Links to topics I talk about in the video:

📖 Reference Books:

🎥 My Recording Gear:

💻 Get Social 💻

#leetcode #programming #interview

[jaxsyntax]

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

[adveshdarvekar]

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.

[rajmahto]

You are inspiration sir, keep similing

[vikashkatiyar]

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

[manishbhardwaj]

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

[XiaoFang-mc]

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

[Maneeshce]

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

[hashcodez]

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).

[ashtonronald]

problem made extremely intuitive, gg!

[sohrab]

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

[_debopriyoghosh_cse_by]

U are great, no idea why u are undeerrated

[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 :)

[just_a_guy]

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

[room]

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

[lalanabiridi]

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

[plutomessi]

bhaiya this code passed 35/44 test cases
class Solution {
public boolean isIsomorphic(String s, String t) {
ArrayList<Integer> s1 = new ArrayList<>();
ArrayList<Integer> 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);
}
}

[samiranroyy]

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<Character, Character> sam = new HashMap<>();
for(int i=0;i<n;i++)
{
char original = s.charAt(i);
char replacedch = t.charAt(i);
//check..


{
sam.put(original, replacedch);
}else{
return false;
}
}else
{
char originalcheck = sam.get(original);

return false;
}
}
return true;
}

} Wrong Answer
35 / 46 testcases passed

Editorial
Input
s =
"paper"
t =
"title"

Use Testcase
Output
false
Expected
true

[abhishekj]

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

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

[mstinku]

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