Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Problem Challenge 1: Permutation in a String (hard)

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"

.....

.....

.....

Like the course? Get enrolled and start learning!
P

priety.33

· 17 days ago


using namespace std;

#include <iostream>
#include <string>
#include <unordered_map>

class Solution {
public:
    bool findPermutation(const string &str, const string &pattern) {
        
        unordered_map<char, int> freq;

        for (auto c: pattern) {
            freq[c] += 1;
        }

        for (int start = 0, end = 0; end < str.size(); end++) {

            freq[str[end]] -= 1;

            while (freq[str[end]] < 0 && start <= end) {

                freq[str[start]] += 1;
                start += 1;

            }

            if (end - start + 1 == pattern.size()) {
                return true;
            }

        }

        return false;
    }
};
Ravi Kishore Thella

Ravi Kishore Thella

· 3 months ago

Since, we are using the lowercase characters in the string, the optimal approach is to use the int[] for storing the frequency count. HashMap has internal overheads and int[26] will be faster. It is a good optimization technique to have in your arsenal.

Show 1 reply
Adam

Adam

· 2 years ago

Instead of maintaining two HashMaps, one for window and the other one for expected frequency, we can use just one.

Initialize the map with the pattern. Every time when a character enters a window, remove it from the pattern map. Every time a character leaves the window, add it to the map.

When count for any character becomes 0, we simply remove the character from the map.

This way we are done when the map becomes empty.

Eventually the number of map lookups becomes much smaller. Even hash map lookup is expected to be O(1), it still is relatively expensive.

S

shanehowe100

· 2 years ago

As mentioned in one of the constraints

  • str and pat consist of lowercase English letters

This means when building our hashmap from pat in the worst case it will grow to O(26) . This is a constant number and can be simplified to O(1)

Show 1 reply
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

The window is fixed in size so the solution should not be that complicated

import math
from collections import Counter
class Solution:
  def findPermutation(self, text, pattern):
    # edge case
    if text == "":
      return False 

    pattern_frq = Counter(pattern)
    text_freq = {}

    # the initial window frequency count
    for i in range(len(pattern)):
      text_freq[text[i]] = text_freq.get(text[i], 0)
      text_freq[text[i]] += 1
      
    # move the window and check the frequencies 
    j = 0
    i = len(pattern) - 1 
    while i < len(text):
      if text_freq == pattern_frq:
        return True
      
      # move i and add the i frequency to the map
      i += 1
      if i == len(text):
        break
      text_freq[text[i]] = text_freq.get(text[i], 0)
K

Kai

· 2 years ago

The constraint says the length of str and pattern is greater than 0.

However, there're test cases with empty string

For example,

  1. str: "", pattern: ""

  2. str: "ab", pattern: ""

Even if the correct constraint is "equal or greater than 0", why #1's expected result is false but #2 is true?

Show 1 reply
sealess

sealess

· 3 years ago

import math

class Solution:

def findPermutation(self, str1, pattern):

if len(str1) < len(pattern):

  return False

if str1 == pattern and len(str1) >0:

  return True

pattern_map = {}

for i in pattern:

  pattern_map[i] = pattern_map.get(i,0)+1

window_len = len(pattern)

start = 0

window_map = {}

for end in range(len(str1)):

  end_char = str1[end]

  window_map[end_char] = window_map.get(end_char, 0)+1

  if end - start +1 > window_len:

    start_char = str1[start]

    window_map[start_char] -=1

    if window_map[start_char] == 0:

      del window_map[start_char]

    start+=1

  if window_map == pattern_map:

    return True

return False
Faraz Ahmed

Faraz Ahmed

· 3 years ago

i dont quite understand this one properly, why we are adding it back to the frequency? my guess is to maintain the matched?? but if the pattern length is 3, and if frequency map contains 3 characters, and we are only decrementing its value, so does it matter we put it back or skip it?? because it will always be there with a lesser frequency maybe

Show 1 reply
P

Popa Stefan

· 3 years ago

So the space complexity is O(E), where E in this case is the size of the alphabet, not the size of the string.

In this case O(E) which asymptotically is O(1)

Show 1 reply
A

arya.javadi80

· 3 years ago

Why do we do frequency[char] = 0 instead of frequency[char] = 1

, and then incrementing it if it appears again? In this case couldn't we get -1 for some values?

Reading Progress

0%

Vote for new content