Technical Interview: Check if string is a permutation

[@kla_youtube]

It's not correct solution. eg. str_1 = "dreiving" str_2 = "drrrring" gives wrong answer. When you replace a character, it will replace all of that particular character.

[@afshinhakimi7298]

You are right, the replace method will replace all of a character as its third optional parameter, count, is set to that way for using this solution in a correct way we need to set it to 1: str_2 = str_2.replace(c, "", 1)

[@prat534]

Brilliant explaination ! However, i think there is a bug in the code. i.e in the replace function we should only be replacing the first instance of the character in second string and not replace them all str_2 = str2.replace(c, "",1)

[@LucidProgramming]

Ah, I think you are correct! Thanks for pointing that out!

[@deserve_it]

I think it will be little more efficient and may be a more effective , depending on length of compared strings if you will add one line to your permutation function . if c in str_2: str_2 = str_2.replace(c,"'") else: return False You don't really need to continue if one of chars is not inside the second string .

[@LucidProgramming]

Very good point! Thanks for the comment and for watching. Cheers!

[@HT-on5sk]

The code is wrong. Try it with s1 = 'hello' and s2 = 'hello'

[@yehiamcp]

It won't give the expected result if you've duplicated characters because replace will replace all duplicated values.

[@심명훈-k4x]

wrong suggestion

[@AhmedAbdelrahmanAtbara]

Looks like you have a problem in this code, go a head and replace 'one letter' in str_1 with any letter of your choice, you will still get output True!! I suggest this: After replace(" ", ""), convert to lists .... str_1 = list(str_1) str_2 = list(str_2) for ... if c in str_2: p = str_2.index(c) del(str_2[p]) Leave the rest of the code the same, only do these changes above.

[@ajaychandrasekaran1158]

Amazing set of Videos.. hats off _/\_ We want more :) :)

[@LucidProgramming]

Thank you! If you like my content, I've been working on some projects during the past couple of months. If you would like to stay up-to-date, please consider subscribing to my mail list. Also, if you haven't already, please consider subscribing! I really appreciate the support. I hope that the content I provide there will enhance the videos on my KZbin page. bit.ly/lp_email

[@neerajankam6196]

How about the following solution? I hope it covers all the edge cases too. A= "the cow jumps over the moon." B= "the cow jumps over the moon." def check_unique(s1,s2): s1 = s1.replace(" ","") s2 = s2.replace(" ", "") return (len(s1) == len(s2) and set(s1) == set(s2)) print(check_unique(A,B))

[@LucidProgramming]

Hi Neeraj. From a quick look, that seems like a valid way to solve the problem. It's always good to try to catch the edge cases yourself, especially as that will be your responsibility in an interview. Thanks for posting your code, and thanks for watching!

[@neerajankam6196]

@@LucidProgramming I tried various edge cases and this seemed to work fine. Your videos are awesome; hoping to see more playlists/ videos in this playlist. Many thanks for all the content on your channel!

[@LucidProgramming]

@@neerajankam6196 I intend to keep the videos going strong! Thanks for your support and encouragement!

[@HT-on5sk]

This code is wrong. Try A = 'driving' and B = 'drivgng'

[@weichengzhu6605]

Hi Lucid, Thank you for your wonderful tutorial. Example: if we take these "ddin" and "dinn" as input, because the len is same and the replace function will replace all the characters in "dinn" to "", right?

[@LucidProgramming]

Hi 朱伟成. Thanks for your comment. And yes, that's correct. Actually, we saw the same behavior with the "driving" example, as the other word we were checking also had the same characters permuted in the string. Hope that helps. Cheers, and thanks for watching!

[@외면해-m6c]

Can I ask why your solution is linear time instead of O(S1) × O(S2) where S1 is the length of str 1 and S2 is the length of str2? For each character in Str 1, we are checking if that character is in the Str2, in operation is O(n).

[@LucidProgramming]

Because it should be additive, not multiplicative

[@andreacosta9576]

**noob time!** Wouldn't sorting the strings be more efficient? For example: def is_perm(s1,s2): s1=s1.replace(" ","") s2=s2.replace(" ","") if len(s1)!=len(s2): return False s1=sorted(s1) s2=sorted(s2) return s1==s2 The sorting would give O(2*n*logn) and the matching O(n). So O(2nlogn) overall. Is this correct?

[@LucidProgramming]

Hi Andrea. So, first let's assume s1 has a length of "n" and s2 has a length of "m". The replace function needs to process each string linearly to eliminate the spaces. O(n + m). Then, after we check the lengths, we know the string lengths must be the same, so sorting does give O(2(n log n)). But, this does not give you O(n). You have an extra log n factor in there.

[@sakshamsingh7599]

Love your code, this is absolutely amazing and efficient code. One question I want to ask that can we sort the string first and then do the comparison because this code will give us the time complexity of O(nlogn) by using merge sort. Can you please describe it?

[@LucidProgramming]

Yeah, you could sort and check. The nlogn would dominate the runtime.

[@Shiva77079]

can we just sort both the strings and if they are equal then it is permutation?

[@LucidProgramming]

You could, although this would incur a factor of O(n log n) for sorting, which is not necessary and would increase the runtime from what is proposed in this video. Hope that makes sense. Cheers!

[@KrzysztofSpikowski]

how about if both strings are identical str1="cat" and str2="cat", it will return True, is this also permutation or not?

[@LucidProgramming]

Technically, it is considered a permutation.

[@aaandrade5]

it doesn't work for "ddrivig"

[@LucidProgramming]

Doesn't work how?

[@aaandrade5]

@@LucidProgramming it gives True, but I've already fixed. "if len(str_1) != len(str_2) or len(set(str_1)) != len(set(str_2)): return False

[@LucidProgramming]

@@aaandrade5 doesn't make sense. What is the other string you are feeding in? It takes two arguments

[@aaandrade5]

@@LucidProgramming "driving" and "ddrivig"

[@aaandrade5]

if len(set(str_1)) != len(set(str_2)): return False, is much better.

[@css7021]

I don't understand why it's showing 'False' for both cases were its True for one of the case. >>>driving #length =7 >>>drivign #length = 7 True should be the o/p but I am getting False

[@roopchandjangir6862]

Because when it find for i, it replace all I in str2 , and u get error while finding for 2nd i in str2

[@lifangmoler998]

how is this different from anagram video ?

[@LucidProgramming]

Hi Lifang. This is different because the definition of an anagram and the definition of a permutation are different. Hope that makes sense, and let me know if not. Cheers!

[@ajaychandrasekaran1158]

@@LucidProgramming I am confused how anagram and permutation are different. Can you please explain?

[@LucidProgramming]

@@ajaychandrasekaran1158 en.wikipedia.org/wiki/Anagram, en.wikipedia.org/wiki/Permutation

[@chintabindhusri9048]

@@ajaychandrasekaran1158 anagram is when you do sorting and permutation is just about the presence of words in the two given strings are same or not.

[@Rich65501]

Here's one solution: def is_permutaion(string1, string2): return sorted(string1.replace(" ","")) == sorted(string2.replace(" ","")) string1 = "chesee is great" string2 = "great is cheese" print(is_permutaion(string1,string2))

[@LucidProgramming]

Nice. However, this solution is O(n log n) as opposed to O(n) due to the sorting. Thanks for sharing though!

[@nolactose3633]

if str_1 is "driving" and str_2 is "ddddddd" in which both are the same length, but it will return True. how can we overcome this?

[@LucidProgramming]

Hi Hisham. You're absolutely right. In fact, if you a check a more recent video on my channel, this issue is fixed: kzbin.info/www/bejne/p5vYiYiNr7uClbM BTkBuH5qIbhshbg_K I wasn't aware of this problem, so thanks for letting me know. Cheers.

[@yingma6770]

Hi, I check the "Is Palindrome", but I still don't know how this issue is fixed. Could you please explain more? @@LucidProgramming

[@LucidProgramming]

@@yingma6770 Hi Ying. If you check the video, I believe the output of the code behaves properly for the input case "driving" and "ddddddd", correct?

[@yingma6770]

Thank you for your reply. But I think that video is to check palindrome, not permutation, right?@@LucidProgramming

[@LucidProgramming]

@@yingma6770 Ah, quite right. Perhaps I should have posted this link here: kzbin.info/www/bejne/i3XQq2logdllZpY&list=PL5tcWHG-UPH03aqnBTkBuH5qIbhshbg_K&index=7 Sorry about that!

[@jonallen3279]

i entered the code and it comes out false every time?

[@LucidProgramming]

Hi Jon. You most likely have an error somewhere. I would recommend checking out the link in the description and downloading the code to see where your code differs from mine. Cheers.

[@hazartilirot1014]

To my mind using .replace() method is an incorrect approach since it should replace all occurrences of a letter in a word. I'm an amateur in coding though I've just tried to deal with issue like that: word_1 = "driving" word_2 = "girvidn" def permutation(word_1, word_2): if len(word_1) != len(word_2): return False else: temp = '' for ch_1 in word_1: for ch_2 in word_2: if ch_1 == ch_2: temp += ch_1 break return len(temp) == len(word_1) print(permutation(word_1, word_2))

[@LucidProgramming]

But we're replacing the spaces with nothing. How is that not exactly what we want?

[@ejazshaikh1732]

My Solution def is_permutation(s1,s2): return sorted(s1.replace(' ',''))==sorted(s2.replace(' ','')) print(is_permutation('The solutions in this series focus','The in solutions focus series this'))

[@LucidProgramming]

That's concise, but your complexity is going to be upper bounded by the sorting giving you O(nlogn), where my solution should just be O(n)

[@rotatingdisk]

just a tiny bug str_2 = str_2.replace(c, "", 1)

[@LucidProgramming]

Why is the "1" there?

[@giorgichanturia1401]

for future add case sensitivity

[@tweede5555]

Hmm just came across this and while python's built in "in" and "replace()" functions are probably fast average case, worst case for "in" is O(n), which I get why people thought the whole algorithm would be O(n^2). The replace method is also O(n) and returns a copy since strings are immutable, but not sure here since you're doing str_2 = str_2.replace... My solution was to use extra space. First go through str_1, put it in a dictionary with the character as key and occurrence as value. Then, go through str_2, if the character is in the dictionary, decrement the occurrence by 1. Once the value of a certain key becomes 0, delete that key value from dictionary. In any case, if something gives us a KeyError, then return false immediately. If not, the size of the dictionary should be 0 at the end. Return true if the size of the dictionary is 0. Time complexity would be O(2n) which is just O(n) and space would be O(n)

[@LucidProgramming]

Nice assessment and thanks for sharing your approach. Cheers, and thanks for watching!

[@ajaychandrasekaran1158]

def check_permutation(st1,st2): if len(st1) != len(st2): return False st1 = st1.lower() st2 = st2.lower() my_dict1 = { } my_dict2 = { } for x in st1: if x not in my_dict1: my_dict1[x] = 1 else: my_dict1[x] += 1 for x in st2: if x not in my_dict2: my_dict2[x] = 1 else: my_dict2[x] += 1 return my_dict1 == my_dict2 st1 = "driving" st2 = "drivign" print(check_permutation(st1,st2)) How about this one?

[@LucidProgramming]

That should work, but it's much worse in terms of time and space complexity.

[@rohitdas480]

should also convert all the elements to lowercase

[@GOSPGABO]

I do in this way def is_permutation(str_1, str_2): str_1 = str_1.replace(" ","") str_2 = str_2.replace(" ","") if len(str_1)!=len(str_2): return False for i in range(len(str_1)): if str_1[i] not in str_2: return False return True

[@LucidProgramming]

Thanks for sharing!

[@SinghSurjeet-wq4eg]

its not a correct solution when you are replacing you should use str_2=str_2.replace(c,"",1) then this will work but the time complexity will increase @lucidProgramming