Check Permutation of Two Strings in Python

Introduction

In the realm of string manipulation and algorithmic problem-solving, determining whether two strings are permutations of each other is a common task. A permutation of a string is a rearrangement of its characters that results in another string. In this article, we will explore various approaches to efficiently check whether two strings are permutations of one another using Python.

Understanding the Problem

Before delving into the solutions, let’s formally define the problem. Given two strings, we want to determine if one string is a permutation of the other. In other words, we need to ascertain if the characters in one string can be rearranged to form the other string.

For example, consider the strings “listen” and “silent“. These two strings are permutations of each other since their characters can be rearranged to form the other string.

Approach 1: Sorting and Comparison

One straightforward way to check if two strings are permutations of each other is to sort both strings and then compare them character by character. If the sorted versions of the two strings match, then they are permutations. Let’s implement this approach:

def are_permutations_sort(str1, str2):
    return sorted(str1.lower()) == sorted(str2.lower())

is_permutation = are_permutations_sort('Listen', 'Silent')

if is_permutation:
    print("Yes, two strings are permutations of one another.")
else:
    print("No, two strings are not permutations of one another.")

Output 

Yes, two strings are permutations of one another.

This approach works efficiently as sorting generally has a time complexity of O(n log n), where ‘n’ is the length of the strings. However, this approach might not be the most optimal in terms of time complexity.

Approach 2: Character Count Comparison

A more efficient approach is to count the occurrences of each character in both strings and then compare the character counts. If the character counts are the same for both strings, they are permutations of each other.

def are_permutations_count(str1, str2):
    if len(str1) != len(str2):
        return False
    
    char_count = [0] * 128  # Assuming ASCII characters
    
    for char in str1:
        char_count[ord(char)] += 1
        
    for char in str2:
        char_count[ord(char)] -= 1
        if char_count[ord(char)] < 0:
            return False
            
    return True

str1 = "Earth"
str2 = "Heart"

is_permutation = are_permutations_count(str1.lower(), str2.lower())

if is_permutation:
    print("Yes, two strings are permutations of one another.")
else:
    print("No, two strings are not permutations of one another.")

Output 

Yes, two strings are permutations of one another.

This approach has a time complexity of O(n), where ‘n’ is the length of the strings, as it involves iterating through the strings once to count characters and then comparing the character counts.

Approach 3: Using Dictionaries

We can also employ dictionaries (hash maps) to solve this problem efficiently. We’ll create a dictionary to store the character frequencies in the first string and then decrement the frequencies using the characters in the second string. If all values in the dictionary become zero, the strings are permutations.

def are_permutations_dict(str1, str2):
    if len(str1) != len(str2):
        return False
    
    char_freq = {}
    
    for char in str1:
        char_freq[char] = char_freq.get(char, 0) + 1
        
    for char in str2:
        if char not in char_freq or char_freq[char] == 0:
            return False
        char_freq[char] -= 1
            
    return True


str1 = "Elbow"
str2 = "Below"

is_permutation = are_permutations_dict(str1.lower(), str2.lower())

if is_permutation:
    print("Yes, two strings are permutations of one another.")
else:
    print("No, two strings are not permutations of one another.")

Output 

Yes, two strings are permutations of one another.

Conclusion

Checking whether two strings are permutations of each other is a common problem with various efficient solutions. The sorting approach, character count comparison, and dictionary-based approach are all viable ways to solve this problem. The choice of approach depends on factors like string length, available memory, and desired time complexity.

When dealing with larger strings or when performance is crucial, the character count comparison or dictionary-based approach is generally more efficient due to their linear time complexity. Understanding these techniques equips developers with the tools to efficiently solve similar string-related problems in Python and other programming languages.