String Processing in Python: Check Permutation

In this video, we will be considering how to determine if a given string is a permutation of another string.

Specifically, we want to solve the problem:
Given two strings, write a function to determine if one is a permutation of the other.

We solve this problem in Python and analyze the time and space complexity of our approach.

This video is part of a series on string processing and, specifically, on how these problems tend to show up in the context of a technical interview:

This video is also part of an "Algorithm" series. For more algorithm tutorials:

The software written in this video is available at:

Do you like the development environment I'm using in this video? It's a customized version of vim that's enhanced for Python development. If you want to see how I set up my vim, I have a series on this here:

If you've found this video helpful and want to stay up-to-date with the latest videos posted on this channel, please subscribe:

[mightyprogrammer]

i think everyone is little bit confused in the second method
so let me clear this out.

why we were decrement the value of d[i] in first loop coz we are checking only one string in first loop
i got it after putting print statement in that
and take a look on this and i hope you will understand :)

code :
def is_perm_2(str_1, str_2):
str_1 = str_1.lower()
str_2 = str_2.lower()

if len(str_1) != len(str_2):
return False

d = dict()
for i in str_1:
if i in d:
d[i] -= 1
else:
d[i] = 1
print(d[i])
print("\n")
for i in str_2:
if i in d:
d[i] -= 1
else:
d[i] = 1
print(d[i])


return all(value == 0 for value in d.values())



not_permutation_1 = "google"
not_permutation_2 = "ooggle"
print(is_perm_2(not_permutation_1, not_permutation_2))

Output :
1
1
0
0
1
1


-1
-2
-1
-2
0
0
False

at the first we were looping, great

As when we decrement the value so we get our value not equal to zero which is not true
so thats why Ans is False

so let me give you second example which is correct

code:
def is_perm_2(str_1, str_2):
str_1 = str_1.lower()
str_2 = str_2.lower()

if len(str_1) != len(str_2):
return False

d = dict()
for i in str_1:
if i in d:
d[i] += 1
else:
d[i] = 1
print(d[i])
print("\n")
for i in str_2:
if i in d:
d[i] -= 1
else:
d[i] = 1
print(d[i])


return all(value == 0 for value in d.values())

not_permutation_1 = "google"
not_permutation_2 = "ooggle"
print(is_perm_2(not_permutation_1, not_permutation_2))

Output:
1
1
2
2
1
1


1
0
1
0
0
0
True

lemme explain this

str_1 : "google"
str_2 : "ooggle"

first time "g" have seen so the value is
1
and then "o" which is also first time so value is
1
move ahead the "o" have seen again so value is
2
move ahead the "g" have seen again so value is
2
move ahead "l" have seen first time
1
move ahead "e" have seen first time
1

second loop

there is "o" already present in dict so decrement the value is
1
again we have meet the "o" so decremnt again the value is
0
there is "g" already present in dict so decrement the value is
1
again we have meet the "g" so decremnt again the value is
0
move ahead we can seen the "l" already present so value is
0
move ahead we can see the "e" already present so the value is
0

hence ANSWER is True

hope you understand :)

Thanks man LUCID for your DS

[SomeOfOthers]

I'm a big fan of your content! It's been really helpful to me and I appreciate it, man. I have a question about your second approach though: Why decrement the count in the first loop? If you were to increment the count and populate the dictionary with letters and counts, then in the second loop, if all the letters in the second string are present in the first, it would bring all the values to zero, wouldn't it?

[shreyaagrawal]

The second method might not work out for words like google or ooggle
Basically words which will have repeated alphabets. Or will it?

[shonnoronha]

At 5:39, instead of using a for loop for checking if the elements are not equal, we could check if str_1 = str_2 then return True, or else return False .
What is the edge case with this one or it can be used. Please explain!
Thank you soo much, love your videos!

[vamsimanubolu]

Using dictionary:
def permu(s1, s2):
s1=s1.replace(' ', '').lower()
s2=s2.replace(' ', '').lower()
d1={}

for i in s1:
if i in d1:
d1[i]+=1
d1[i]=1
for i in s2:
if i in d1:
d1[i]-=1
else:
return False
else:
return True

[captain_vegan]

Line 42 (11:29) in the first for loop should be "+=" not "-="

[Dev-dkez]

The second method doesn't look right to me. The value of key has to be assign 0 in case the key is already present instead of subtracting. See below:
for i in str_1:
if i in d:
d[i] = 0
else:
d[i] = 1
for i in str_2:
if i in d:
d[i] = 0
else:
d[i] = 1

[Samcreature]

For is_perm_1, couldn't you just return "str_1 == str_2" after doing the join? I don't see the need to loop through each character afterwards and confirm that they are equal

[AnhChimXanh]

What's the different between anagram and permutation?, if you write print(is_perm_1('fairy tales', 'rail safety')) it return True, doesn't that mean anagram is permutation, and btw the github link is no longer valid :D

yeah the 2nd has a logical error...dude man