Detect permutation in string

Question

Given two strings, determine if one string is a permutation of the other. The input consists of two strings, and the output should be a boolean value indicating whether the second string can be formed by rearranging the characters of the first string. Consider case sensitivity and ignore spaces.

Codemia · Accepted Answer

To determine if one string is a permutation of another, we can recognize that both strings must contain the same characters with the same frequencies. This problem can be approached using a frequency count method, which is efficient and straightforward. Since we need to consider case sensitivity and ignore spaces, we must ensure that our character counting takes these factors into account. The most suitable pattern for this is counting characters, which can be effectively implemented using a hash map (dictionary in Python) to track character counts.

1. **Normalize the Strings**: Remove spaces and convert both strings to the same case. For example, if we have `s1 = 'Listen '` and `s2 = 'Silent'`, we would process them to `s1_normalized = 'listen'` and `s2_normalized = 'silent'`.
2. **Count Characters**: Create a frequency count of characters for the first string. For `s1_normalized = 'listen'`, we would have a count like: `{'l': 1, 'i': 1, 's': 1, 't': 1, 'e': 1, 'n': 1}`.
3. **Compare Counts**: For the second string, decrement the counts based on the characters in `s2_normalized`. If at any point a character count goes negative or if there are any leftover counts after processing `s2_normalized`, then `s2` is not a permutation of `s1`. This can be done in a single pass through both strings.

```python
def are_permutations(s1: str, s2: str) -> bool:
    # Step 1: Normalize the strings by removing spaces and converting to lowercase
    s1_normalized = s1.replace(' ', '').lower()
    s2_normalized = s2.replace(' ', '').lower()

# Step 2: Check if lengths are equal
    if len(s1_normalized) != len(s2_normalized):
        return False

# Step 3: Count characters in s1_normalized
    char_count = {}
    for char in s1_normalized:
        char_count[char] = char_count.get(char, 0) + 1

# Step 4: Decrement counts based on s2_normalized
    for char in s2_normalized:
        if char in char_count:
            char_count[char] -= 1
            if char_count[char] < 0:
                return False
        else:
            return False

return True  # All counts should be zero if they are permutations
```
This code effectively checks if `s2` is a permutation of `s1` by counting and comparing character frequencies.

The time complexity of this solution is O(n), where n is the length of the longer string, since we iterate through each string once. The space complexity is O(1) relative to the character set used (assuming only ASCII characters, this is constant space for the hash map). This efficiency is crucial, especially in scenarios with longer strings, and the algorithm remains optimal within the given constraints.

1. **Empty Strings**: Both strings are empty, which should return True since they are permutations of each other.
2. **Different Lengths**: If the strings have different lengths, such as `s1 = 'abc'` and `s2 = 'ab'`, the function should return False.
3. **Case Sensitivity**: Inputs like `s1 = 'aBc '` and `s2 = 'cba'` should return True after normalization (ignoring spaces and considering case).
4. **Spaces Handling**: Strings with only spaces like `s1 = '   '` and `s2 = ' '` should return True after normalization. All these edge cases must be addressed to ensure robustness.

Detect permutation in string

Confluent

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

Confluent 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