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

0% completed

Vote For New Content
Problem Challenge 1: Permutation in a String (hard)
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.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

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