Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Problem Challenge 1: Permutation in a String
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

Given a string and a pattern, find out if the string contains any permutation of the pattern.

Permutation is defined as the re-arranging of the characters of the string. For example, “abc” has the following six permutations:

  1. abc
  2. acb
  3. bac
  4. bca
  5. cab
  6. cba

If a string has ‘n’ distinct characters, it will have n! permutations.

Example 1:

Input: str="oidbcaf", pattern="abc"   
Output: true   
Explanation: The string contains "bca" which is a permutation of the given pattern.

Example 2:

Input: str="odicf", pattern="dc"   
Output: false  
Explanation: No permutation of the pattern is present in the given string as a substring.

Example 3:

Input: str="bcdxabcdy", pattern="bcdyabcdx"  
Output: true  
Explanation: Both the string and the pattern are a permutation of each other.

Example 4:

Input: str="aaacb", pattern="abc"  
Output: true  
Explanation: The string contains "acb" which is a permutation of the given pattern.

Constraints:

  • 1 <= str.length, pat.length <= 10<sup>4</sup>
  • str and pat consist of lowercase English letters.

Solution

To solve this problem, we use a sliding window technique combined with a hashmap to keep track of character frequencies. The sliding window allows us to check each substring of the input string efficiently. The hashmap stores the count of each character in the pattern. As we slide the window over the string, we compare the character counts of the current window with those in the hashmap. This approach ensures that we only check substrings that are the same length as the pattern, which makes it very efficient.

The reason this approach is effective is due to its linear time complexity. Instead of generating all possible substrings, we slide a window of fixed size across the string and update our counts dynamically. This reduces the number of comparisons and allows us to quickly determine if a permutation of the pattern exists in the string. It is the most efficient approach as it combines the benefits of the sliding window and hashmap for constant time lookups and updates.

Step-by-step Algorithm

  • Initialization:

    • Create a hashmap to store the frequency of each character in the pattern.
    • Initialize the windowStart pointer and matchedCount to 0.

  • Sliding Window Iterations:

    • For each character in the string (using windowEnd as the end pointer):
      • Check if the character is in the pattern's frequency map.
      • If it is, decrement its count in the map.
      • If the character's count in the map reaches 0, increment the matched count.
      • If the size of the window exceeds the pattern length:
        • Remove the leftmost character (at windowStart) from the window.
        • If the leftmost character is in the pattern's frequency map:
          • If its count was 0, decrement the matched count.
          • Increment the character's count back in the map.
      • Check if the matched count equals the number of unique characters in the pattern:
        • If it does, return true.

Algorithm Walkthrough

Let's go through the algorithm using the example: str = "aaacb", pattern = "abc"

  1. Initialization:

    • Pattern frequency: {a: 1, b: 1, c: 1}
    • Window Start: 0
    • Matched characters count: 0

  2. First Iteration (windowEnd = 0):

    • Current window: a
    • Right character: a
    • Updated pattern frequency: {a: 0, b: 1, c: 1}
    • matched count: 1 (since a frequency is now 0)

  3. Second Iteration (windowEnd = 1):

    • Current window: aa
    • Right character: a
    • Updated pattern frequency: {a: -1, b: 1, c: 1}
    • matched count: 1 (no change since a frequency is less than 0)

  4. Third Iteration (windowEnd = 2):

    • Current window: aaa
    • Right character: a
    • Updated pattern frequency: {a: -2, b: 1, c: 1}
    • matched count: 1 (no change since a frequency is less than 0)
    • windowEnd(2) >= pattern.length() - 1. So, increment windowStart and decrement frequency of str[windowStart] in the map.
    • Updated pattern frequency: {a: -1, b: 1, c: 1}

  5. Fourth Iteration (windowEnd = 3):

    • Current window: aaac
    • Right character: c
    • Updated pattern frequency: {a: -1, b: 1, c: 0}
    • matched count: 2 (since c frequency is now 0)
    • windowEnd(2) >= pattern.length() - 1. So, increment windowStart and decrement frequency of str[windowStart] in the map.
    • Updated pattern frequency: {a: 0, b: 1, c: 0}

  6. Fifth Iteration (windowEnd = 4):

    • Current window: aaacb
    • Right character: b
    • Updated pattern frequency: {a: 0, b: 0, c: 0}
    • matched count: 3 (since b frequency is now 0)
    • Since matched count is equal to the size of the pattern (3), return true

Code  

Here is what our algorithm will look like:

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  • Creating the frequency map: The algorithm first creates a frequency map of the characters in the pattern. This step takes O(M) time, where M is the length of the pattern.

  • Sliding window traversal: The algorithm uses a sliding window approach to traverse through the string. The outer loop runs for each character in the string, so the loop runs O(N) times, where N is the length of the input string.

  • Character frequency updates: For each character in the window, the algorithm performs constant-time operations like updating the frequency in the charFrequencyMap and adjusting the matched count. These operations take O(1) time on average, as hash map operations like put() and get() are constant on average.

  • Therefore, the total time complexity is O(N + M), where N is the length of the input string and M is the length of the pattern.

Overall time complexity: O(N + M).

Space Complexity

  • HashMap space: The algorithm uses a hash map, charFrequencyMap, to store the frequency of characters in the pattern. This requires O(M) space, where M is the number of unique characters in the pattern.

  • Additional variables: The algorithm uses a few extra variables (windowStart, windowEnd, matched), all of which require constant space, O(1). No additional data structures are used that depend on the input size.

Overall space complexity: O(M), where M is the number of unique characters in the pattern.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible