Grokking the Coding Interview: Patterns for Coding Questions

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!
J

Joshua Causey

· 5 years ago

Should we be able to answer the problem challenges on our own after going through the previous challenges? Is it okay that for some things I still need to look at the solution?

Show 4 replies
V

Viktor

· 4 years ago

Hey, I don't understand how "if window_end >= len(pattern) - 1" check works for "If the window size is greater than the length of the pattern, shrink the window to make it equal to the pattern’s size". Because here we never subtract window_start from window_end. So actually, we shrink on every iteration starting from window_end is equal to pattern size. Hmm...

Show 1 reply
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
C

Clodoaldo Favaro

· 4 years ago

I've done it like this: using 2 hashMaps, one of them to "reset" the original hashMap when we find a character that's not in the pattern. Image

Show 1 reply
V

Viacheslav Lushchinskiy

· 4 years ago

Actually, no windows shrinking is required to solve the task. We jus go forward and keep track if we found a pattern or not. Just rephrase the task like this: Find out if there is a substring in a string that contains the same characters as in the pattern regardless the order. The task now becomes much simpler :) Solution in JS:

const f = (_str, _pattern) => { let patternLength = _pattern.length; let numberOfMatches = 0;

//transform to an array to use the splice method let _patternArr = [..._pattern];

// Algorithm idea: all the char in the pattern regardless the order // should be found in a substring.

//Just reset the pattern if a foreign char is found for (let windowEnd = 0; windowEnd < _str.length; windowEnd++) { const rightChar = _str[windowEnd]; const index = _patternArr.indexOf

C

Christian Salinas

· 4 years ago

I personally like going without the matched variable and instead checking if the character frequency for the pattern is zero. Something like this in python:

if all(v ==0 for v in char_frequency.values()): return True

Show 2 replies
A

Anthony DiFede

· 4 years ago

Can someone help me with the time/space complexity of this solution?

Image

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?

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
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