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

Problem: Permutation in String

Explore how to identify if a string contains any permutation of another by using a fixed-size sliding window and character frequency tracking. Learn to implement this technique in Java, efficiently checking substring anagrams 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.

Java
usercode > Solution.java
import java.util.*;
class Solution {
    public boolean checkInclusion(String s1, String s2) {
        // Replace this placeholder return statement with your code
        return false;
    }
}
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 in s1Count ...