Permutation In String Leetcode Problem 567 [Python Solution]

Welcome to another Python coding tutorial!

In this blog post, we’ll tackle the LeetCode problem titled “Permutations II.” The problem can be found at this link.

We’ll provide a detailed Python solution to this problem, explain the reasoning behind our approach, and discuss time and space complexity.

Problem Overview

The problem statement is as follows:

Given a collection of numbers, nums, that might contain duplicates, your task is to return all possible unique permutations in any order.

Let’s illustrate this with an example.

Example 1:

Input: nums = [1, 1, 2]
Output:

[[1, 1, 2],
[1, 2, 1],
[2, 1, 1]]


Example 2:

Input: nums = [1, 2, 3]
Output:

[[1, 2, 3],
[1, 3, 2],
[2, 1, 3],
[2, 3, 1],
[3, 1, 2],
[3, 2, 1]]


Understanding Constraints

Before we dive into the Python code solution, let’s understand the constraints provided in the problem:

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

These constraints indicate that the input list nums can contain up to 8 elements, and each element can be any integer between -10 and 10.

Permutations II LeetCode Problem Solution

We will approach this problem with a more efficient solution that has a time complexity of O(n).

Instead of generating all possible permutations and then filtering out duplicates, we’ll use a sliding window approach.

1. Bruteforce Approach

A straightforward brute force approach is to generate all permutations of the given numbers, and then eliminate duplicates.

This can be done using the itertools library in Python.

However, this approach has a high time complexity and may not be efficient, especially for large inputs.

We’ll focus on the more efficient approach in this blog post.

2. An Efficient Approach with Sliding Window

The efficient approach is based on a sliding window technique.

We’ll create two count arrays to keep track of the characters in both s1 (the target string) and the current window in s2.

By comparing these count arrays, we can determine if the characters in the window of s2 form a permutation of s1.

Here’s the Python code for the efficient solution:

def checkInclusion(s1: str, s2: str) -> bool:
    if len(s1) > len(s2):
        return False

    s1Count, s2Count = [0] * 26, [0] * 26

    # Initialize the count arrays for s1 and the initial window in s2
    for i in range(len(s1)):
        s1Count[ord(s1[i]) - ord("a")] += 1
        s2Count[ord(s2[i]) - ord("a")] += 1

    matches = 0  # Number of character matches

    # Check if the initial window is a permutation of s1
    for i in range(26):
        matches += 1 if s1Count[i] == s2Count[i] else 0

    l = 0  # Left pointer for the sliding window

    # Move the window to the right and update counts
    for r in range(len(s1), len(s2)):
        if matches == 26:
            return True  # We found a permutation

        # Update the counts for the new character on the right
        index = ord(s2[r]) - ord("a")
        s2Count[index] += 1

        # Update matches based on the changes
        if s1Count[index] == s2Count[index]:
            matches += 1
        elif s1Count[index] + 1 == s2Count[index]:
            matches -= 1

        # Remove the character on the left and update counts
        index = ord(s2[l]) - ord("a")
        s2Count[index] -= 1

        # Update matches based on the changes
        if s1Count[index] == s2Count[index]:
            matches += 1
        elif s1Count[index] - 1 == s2Count[index]:
            matches -= 1

        l += 1  # Move the left pointer

    return matches == 26  # Check matches for the last window

This solution efficiently checks if there exists a permutation of s1 in s2.

If it does, the function returns True.

Otherwise, it returns False.

Time and Space Complexity

Now, let’s analyze the time and space complexity of our efficient solution.

• Time Complexity: The time complexity is O(n), where n is the length of the string s2.

We iterate through s2 only once, and the operations inside the loop are constant time.

• Space Complexity: The space complexity is O(1) because we use a fixed-size count array of size 26 for both s1Count and s2Count.

Regardless of the input string lengths, the space used remains constant.

Reasoning Behind Our Approach

The reasoning behind our approach is based on the sliding window technique and maintaining two count arrays for s1 and the current window in s2.

We efficiently compare these counts to check for a permutation.

The key insight is that we don’t need to generate all possible permutations, and we can determine whether a permutation exists in s2 by looking at character counts.

This approach significantly reduces the time complexity.

Conclusion

In this blog post, we’ve explored an efficient Python solution to the “Permutations II” problem on LeetCode.

We used the sliding window technique and character count arrays to check for the existence of a permutation of s1 in s2.

The code provides a clear and optimized solution to this problem.

If you found this tutorial helpful, please consider liking and subscribing to our our platform for more Python coding tutorials.

If you have any questions, suggestions, or feedback, please feel free to comment below.

Happy coding, and keep exploring the world of Python programming!