Check Permutation of two strings in Python - most efficiently

Introduction

You are on this page so, I'm assuming you are familiar with permutation more or less. If not, then just take a quick recap about it.

In a word, permutation means a process or act for rearranging the linear order of an ordered or unordered set. During school days we often used to solve permutation problems in mathematics.

In this section, we will solve such a problem, but using a programming language. Here, we will create a python program to check if two strings are permutations of each other.

We will create two solutions for this task. Before that let's talk about something else. Here, we are assuming the following criteria:

1. The strings are case-sensitive. For example, 'PySeek' and 'ypseke' are not the same.

2. The given strings are ASCII strings and the length is less than 128.

3. White spaces are significant. For example, "Julia    " and "Julia" are not a permutation of each other.

Solution #1: Sort the strings and compare

If two strings are permutation of each other which means the length of both are the same and both have the same characters but in a different order.

So, if we sort both of them, the characters of both strings will rearrange in the same order which will imply they are permutations of each other.

Here, we will create a program that will sort two given strings first and then, compare them with each other. Let's dive into the code directly.

Code

def checkPermutation(str1, str2):
    # if length of both strings are not same
    # return False
    if len(str1) != len(str2):
        return False

    # sorting two strings and comparing with
    # each other
    if sorted(str1) == sorted(str2):
        return True

if __name__ == "__main__":
    # two strings
    str1 = "PySeek"
    str2 = "SeePyk"
    # passing two strings to check if
    # one is permutation of other or not
    if checkPermutation(str1, str2):
        print("Yes")
    else:
        print("No")

Output

Yes

For this program, the time complexity depends on the sorting technique we used. By the way, we applied the sorted() method to do that.

Applying an efficient sorting algorithm(for example, the quick sort with O(nlogn) time) for this simple problem can make the program harder.

Solution #2: Check whether both of the strings have identical characters count

You may have noticed that two strings that are permutations of each other have the same character count. We will use this logic here to solve the problem.

Steps

1. First, we will check whether the length of the two strings is same or not. If yes, you can move on to the next step.

2. Create an empty list, length of 128, containing only 0 numbers.

3. Iterate through the first string and count the number of presence of each character(for example, 'c' represents the character) and increase the value at 'index' of that list(declared just before) where 'index' refers to the ASCII value of the 'c' character.

4. Once, the previous step is completed successfully, we will compare the number of presence of each character from the second string with the number, we stored in the list we had declared at step 2.

Code

def permutation(str1, str2):
    # if length of both strings are not same
    # return False
    if len(str1) != len(str2):
        return False

    # declaring a list of 128 length
    # containing only 0 numbers
    letters = [0 for i in range(128)]

    for c in str1:
        # increasing value at ord(c) by 1.
        # ord(c) represents ASCII value of char 'c'
        letters[ord(c)] += 1

    for i in range(0, len(str2)):
        # 'index' stores ascii value of char at index
        # 'i' of str2 list
        index = ord(str2[i])
        # decreasing the value at 'index' of 'letters' list
        # by 1 
        letters[index] -= 1
        # if any value found below 0
        # it will return False
        if letters[index] < 0:
            return False

    return True

if __name__ == "__main__":
    # two strings
    str1 = "PySeek"
    str2 = "SeePy"
    # passing two strings to check if
    # one is permutation of other or not
    if permutation(str1, str2):
        print("Yes")
    else:
        print("No")

Output

No