Introduction
String manipulation is a fundamental concept in programming, often requiring checks for uniqueness and permutations. In this blog, we explore two essential problems:
Checking if a string has all unique characters
Checking if two strings are permutations of each other
We'll use Python to implement efficient solutions for both problems.
1. Checking If a String Has All Unique Characters
Why Is This Important?
Before using a string for passwords, encryption keys, or unique identifiers, it’s often necessary to verify that all characters in the string are distinct.
Efficient Approach Using a Set
A set in Python stores unique elements and allows O(1) average time complexity for lookups. We can iterate through the string and check for duplicates efficiently.
Time Complexity Analysis
Best Case: O(1) (If a duplicate is found early)
Worst Case: O(n) (All unique characters, iterating through the entire string)
Space Complexity: O(n) (Since we store characters in a set)
2. Checking If Two Strings Are Permutations of Each Other
Understanding Permutations
Two strings are permutations of each other if they contain the same characters in the same frequency but in a different order.
For example: ✅ "listen" and "silent" are permutations. ❌ "hello" and "world" are not permutations.
Efficient Approach Using a Frequency Map
Instead of sorting (which takes O(n log n) time), we can use a dictionary (hash map) to store character counts and compare both strings in O(n) time.
Time Complexity Analysis
O(n) (One pass for each string)
Space Complexity: O(n) (Dictionary storage for character frequencies)
Comments