Technical Interview: Check if string is a permutation

Problem: Given two strings, write a function to decide if one is a permutation of the other.

This video is part of the "Technical Interview Problems" series on various problems that arise in a technical interview setting. The solutions in this series focus on the Python language:

The code used in this video may be found here:

[prat]

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)

[ajaychandrasekaran]

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

[weichengzhu]

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?

[sakshamsingh]

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?

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

[Shiva]

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

[yzjucee]

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

[jonallen]

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

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

[rotatingdisk]

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

[andreacosta]

**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?

[KrzysztofSpikowski]

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

[lifangmoler]

how is this different from anagram video ?

[nolactose]

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

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

[neerajankam]

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

[hazartilirot]

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

        return False
    else:
        temp = ''
        for ch_1 in word_1:



                    break


print(permutation(word_1,  word_2))

[tweede]

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)

[css]

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

[aaandrade]

it doesn't work for "ddrivig"