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

Problem: Permutation in String

Discover how to determine if one string contains any permutation of another as a substring. Explore using a fixed-size sliding window alongside character frequency counts to efficiently check for anagrams with optimal time and space complexity. This lesson guides you through implementing this approach in JavaScript, enhancing your understanding of string algorithms and sliding window techniques.

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