Detect permutation in matrix

Question

Given two strings, determine if one string is a permutation of the other. The function should take two input strings and return a boolean indicating whether the second string can be formed by rearranging the characters of the first string. The solution should handle cases with varying character counts and ignore spaces and case differences.

Codemia · Accepted Answer

To determine if one string is a permutation of another, we need to identify if both strings contain the same characters with the same frequencies, regardless of their order. This suggests that we can use a frequency counting approach, where we count how many times each character appears in both strings and compare these counts. The two-pointer technique or a hash-map can be utilized here, but given the need to count and compare characters, using a hash-map (or dictionary in Python) is more appropriate.

1. **Input Normalization**: First, trim any spaces and convert both strings to the same case (e.g., lowercase) to ensure case insensitivity. 
2. **Frequency Counting**: Create a frequency dictionary for the first string (let's call it `str1`). Loop through each character in `str1`, and count how many times each character appears. 
3. **Comparison**: For each character in the second string (`str2`), decrement the corresponding count in the dictionary. 
4. **Final Check**: If all counts in the dictionary return to zero, `str2` is a valid permutation of `str1`. Otherwise, it is not.

**Example**: 
For `str1 = 'Listen'` and `str2 = 'Silent'`, after normalization we have `str1 = 'listen'` and `str2 = 'silent'.` Counting characters gives us:
- `str1`: {'l': 1, 'i': 1, 's': 1, 't': 1, 'e': 1, 'n': 1}
- `str2`: As we loop through `str2`, we reduce counts: {'l': 0, 'i': 0, 's': 0, 't': 0, 'e': 0, 'n': 0}
Since all counts are zero, `str2` is a permutation of `str1`.

```python
def are_permutations(str1: str, str2: str) -> bool:
    # Normalize inputs: remove spaces and convert to lowercase
    str1 = str1.replace(' ', '').lower()
    str2 = str2.replace(' ', '').lower()

# Early exit if lengths are different
    if len(str1) != len(str2):
        return False

# Frequency counting
    char_count = {}
    for char in str1:
        char_count[char] = char_count.get(char, 0) + 1

for char in str2:
        if char in char_count:
            char_count[char] -= 1
            if char_count[char] < 0:
                return False
        else:
            return False

# Check all counts are zero
    return all(count == 0 for count in char_count.values())
```

The time complexity of this approach is O(n), where n is the length of the strings. This is because we traverse each string once to create the frequency dictionary and once again to compare counts. The space complexity is O(1) in terms of character storage since the maximum number of characters (if we only consider the English alphabet) is constant (26 for lowercase letters). Thus, the space used by the dictionary remains constant.

1. **Empty Strings**: Both strings are empty; they are considered permutations of each other (return True). 
2. **Different Lengths**: If one string is longer than the other, they cannot be permutations (return False). 
3. **Special Characters**: If strings contain special characters or numbers, we need to ensure the frequency comparison handles them correctly. 
4. **Spaces**: Leading, trailing, or multiple spaces should be ignored. 
5. **Case Sensitivity**: Ensure that 'A' and 'a' are treated as the same character.

Detect permutation in matrix

Adobe

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Adobe Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string