Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms in JavaScript

Problem: Permutation in String

Explore how to determine if one string contains a permutation of another by using a fixed-size sliding window and character frequency counts. Understand the approach to efficiently check for anagrams in substrings and optimize your solution with O(n) time and constant space complexity.

We'll cover the following...

Statement

Given two strings s1 and s2, determine whether s2 contains any permutation of s1 as a substring. Return true if such a substring exists, and false otherwise.

Note: A permutation of a string is any rearrangement of its characters. You need to check whether any contiguous substring of s2 is an anagram of s1.

Constraints:

  • 1≤1 \leq s1.length, s2.length ≤104\leq 10^4

  • s1 and s2 consist of lowercase English letters.

Examples

canvasAnimation-image
1 / 4

Try it yourself!

Implement your solution in the following coding playground.

JavaScript
usercode > Solution.js
function checkInclusion(s1, s2) {
    // Replace this placeholder return statement with your code
    return -1;
}
export {checkInclusion};
Permutation in String

Solution

The core idea is to use a fixed-size sliding window over s2 with a length equal to s1, along with character-frequency counting, to determine whether any window is a permutation of s1. Instead of comparing full frequency arrays at every step (which would cost O(26)O(26) per slide), we maintain a matches variable that tracks how many of the 2626 lowercase letters currently have equal counts ...