Design Gurus Logo
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"   
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
. . . .

.....

.....

.....

Unlock this and all other premium problems.
No code editor for this lesson
This lesson focuses on concepts and theory