Technical Interview Question

Given two strings s1 and s2, write a function to determine if s2 is a permutation of s1.

A permutation of a string is another string that contains the same characters, but possibly in a different order.

You may assume that the inputs are valid strings with lowercase letters only.

Implement the function isPermutation(s1: str, s2: str) -> bool which returns a boolean value True if s2 is a permutation of s1, and False otherwise.

Example

Input:

s1 = "abc"
s2 = "cba"

Output:

True

Note

In the given example, s2 is a permutation of s1 as both strings have the same characters "a", "b", and "c", but in different orders.

Answer

To determine if s2 is a permutation of s1, we can use the sliding window technique.

The idea is to use two pointers - left and right - to create a sliding window of size len(s1) within s2. We then compare the characters within the sliding window with the characters of s1 to check if they match.

The algorithm can be implemented as follows:

1. Initialize two dictionaries - s1_count and s2_count - to store the frequency/count of each character in s1 and the current sliding window of s2, respectively.

2. Iterate through each character c in s1:

   • If c is not already present in s1_count, set its count to 1.
   • Otherwise, increment its count by 1.

3. Initialize two pointers, left and right, to track the start and end of the sliding window. Set both pointers to 0 initially.

4. While the right pointer is less than the length of s2:

   • If the character at right index of s2 is present in s1_count, increment its count in s2_count.

   • Increment right by 1.

   • Once the length of the sliding window (i.e., right - left) becomes equal to the length of s1:

     • If s1_count and s2_count are equal, return True.
     • Decrement the count of the character at left index of s2 in s2_count.
     • If the count becomes 0, remove the character from s2_count.
     • Increment left by 1.

5. If no match is found, return False.

The time complexity of this algorithm is O(n), where n is the length of s2. This is because we iterate through s2 only once.

The space complexity is O(k), where k is the number of unique characters in s1. This is because we store the frequency/count of each character in s1 in the dictionary s1_count.

Python Implementation:

def isPermutation(s1: str, s2: str) -> bool:
    s1_count = {}
    s2_count = {}

    for c in s1:
        s1_count[c] = s1_count.get(c, 0) + 1

    left = 0
    right = 0

    while right < len(s2):
        if s2[right] in s1_count:
            s2_count[s2[right]] = s2_count.get(s2[right], 0) + 1

        right += 1

        if right - left == len(s1):
            if s1_count == s2_count:
                return True
            
            s2_count[s2[left]] -= 1
            if s2_count[s2[left]] == 0:
                del s2_count[s2[left]]
            
            left += 1

    return False

Summary

The above algorithm uses the sliding window technique to determine if s2 is a permutation of s1. By comparing the frequency/count of characters in s2 within the sliding window with the count of characters in s1, we can check if they match. This approach ensures an efficient way to solve the problem with a time complexity of O(n) and a space complexity of O(k).