Permutation in String

You can check if s2 contains a permutation of s1 by using a sliding window approach combined with the concept of frequency counts.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from collections import Counter

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        s1_len, s2_len = len(s1), len(s2)
        s1_count = Counter(s1)
        window_count = Counter()

        for i in range(s2_len):
            # Add current character to the window
            window_count[s2[i]] += 1

            # If window size exceeds s1's length, remove the leftmost character
            if i >= s1_len:
                if window_count[s2[i - s1_len]] == 1:
                    del window_count[s2[i - s1_len]]
                else:
                    window_count[s2[i - s1_len]] -= 1

            # If the window's count matches s1's count, a permutation is found
            if window_count == s1_count:
                return True

        return False

Explanation

Create Counters: You create counters for s1 and a window of characters in s2. s1_count holds the frequency of each character in s1, and window_count will keep track of the characters in the current window of s2.
Sliding Window: You iterate through s2 and at each step, add the current character to the window (increasing its count in window_count).
Adjust Window Size: If the window size becomes greater than the length of s1, you remove the leftmost character from the window.
Check Permutation: If at any step the window_count matches s1_count, that means the current window in s2 is a permutation of s1, and you return True.
Final Result: If no permutation is found, you return False.

Insights

Sliding Window: The use of a sliding window of the same length as s1 ensures that you only consider substrings of s2 that could possibly be permutations of s1.
Time Complexity: The time complexity of this solution is (O(n)), where (n) is the length of s2, as you iterate through s2 once.
Space Complexity: The space complexity is (O(1)) since the counters will hold at most 26 characters (all lowercase English letters).

Define the Terms Permutation: One of several possible variations, in which a set or number of things can be ordered or arranged.

abc cab cba …

Define the Interface Input: string s1, string s2 Output: boolean

Analyze the Input and Output

Identify the Invariants We cannot change the order in which the characters appear in string s1.

Identify the constraints

The input strings only contain lower case letters.
The length of both given strings is in range [1, 10,000].

We cannot create substrings, it will be inefficient.

Search the Problem Space

Classify the Problem

Analyze the Examples

Solve the Problem by Hand

Describe the Pattern

Distill the Observations to Create Insights

Brute Force Approach

Take every substring of length of s1 in s2 Sort the substring Check if it is equal to the sorted version of s1.

Time: O(N * M Log N) + O(N) Space: O(1)

Analyze Time and Space Complexity

Outline the Solution

Keep the frequency of all the characters in s1 array frequency counter
Scan through the string s2 and check if the substring is consisting of the same frequency as you have for s1 frequency counter.
We can think of the substring size in s2 as a fixed window size equal to s1 length.
Keep moving this window from left to right looking for the permutation using the frequency counter.
Sort both strings

“ab” s2 = “eidbaooo” becomes ‘ab’, “abdeiooo” This approach will violate the invariant and transform the problem to a different problem. We will solve the wrong problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# @param {String} s1
# @param {String} s2
# @return {Boolean}
def check_inclusion(s1, s2)
  goal = Array.new(26, 0)
  current = Array.new(26, 0)

  s1.chars.each do |c|
     goal[c.ord - 'a'.ord] += 1 
  end

  for i in (0...s2.size)
     current[s2[i].ord - 'a'.ord] += 1

#      If the window size exceeds the size of s1
#       we need drop of the character leaving the window
     if i >= s1.size
        current_index = s2[i - s1.size]
        current[current_index.ord - 'a'.ord] -= 1
     end

     if goal == current
         return true
     end
  end

    return false
end

title: Permutation in String excerpt: Code for Permutation in String and Find All Anagrams in a String problems. tags: array-frequency-counter ascii-code

Solution

Comments explaining the code that I found online.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def check_inclusion(s1, s2)
  goal = Array.new(26, 0)
  current = Array.new(26, 0)
    
  s1.chars.each do |c|
    goal[c.ord - 'a'.ord] += 1 
  end
    
  for i in (0..s2.size-1)
    current[s2[i].ord - 'a'.ord] += 1  
     
    # If the window size exceeds the size of s1
    # we need drop the character leaving the window
    if i >= s1.size
      current_index = s2[i - s1.size]
      current[current_index.ord - 'a'.ord] -= 1
    end
      
    if goal == current
      return true
    end
  end
    
  return false
end

With a few modifications, we can make the code work to solve Find All Anagrams in a String problem:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def find_anagrams(s2, s1)
  output = []
  goal = Array.new(26, 0)
  current = Array.new(26, 0)
    
  s1.chars.each do |c|
    goal[c.ord - 'a'.ord] += 1 
  end
    
  for i in (0..s2.size-1)
    current[s2[i].ord - 'a'.ord] += 1  
     
    #  If the window size exceeds the size of s1
    #  we need drop of the character leaving the window
    if i >= s1.size
      current_index = s2[i - s1.size]
      current[current_index.ord - 'a'.ord] -= 1
    end
      
    if goal == current
      output << (i - s1.size + 1)
    end
  end
    
  return output 
end

Building Block

Array as Frequency Counter