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

Problem: Permutation in String

Explore how to detect if one string contains any permutation of another as a substring by applying the sliding window approach and character frequency comparison. Understand how to efficiently track matching character counts to solve string anagram problems with optimal time and 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.

C++
usercode > Solution.cpp
bool checkInclusion(string s1, string s2) {
    
    // Replace this placeholder return statement with your code
    return true;
}
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 ...