Permutation Inclusion — Problem Statement & Solution Guide

Sliding WindowMediumSliding Window / Hash Map

TimeO(n + m)

SpaceO(1)

Problem Description

Given two strings, **key** and **message**, determine whether any permutation of **key** appears as a contiguous substring within **message**. Return true if such a substring exists; otherwise, return false. The solution must run in linear time relative to the length of **message** and use only O(1) additional space aside from the fixed-size character frequency table.

DSA Pattern Breakdown

"Permutation Inclusion"

medium

WHY DOES IT MATTER?

Sliding‑window with frequency counting turns a potentially exponential permutation search into a linear scan, which is essential for real‑time text analysis, intrusion detection, and DNA motif searching where input sizes are massive.

OPTIMIZATION CHALLENGE

The breakthrough is realizing that adding one character and removing another changes the frequency table by only two entries, allowing us to update a mismatch counter in constant time instead of recomputing the whole table.

REAL-WORLD CONNECTION

Think of a conveyor belt (the message) where a quality‑control sensor (the window) continuously checks a fixed‑size batch of items against a known defect pattern (the key). The sensor only needs to remember the current batch, not the entire belt history.

When coding, first write the static frequency table for the key, then slide the window while updating counts and a single integer that tracks mismatches; this avoids costly array comparisons and keeps the implementation clean.

COMPLEXITY AT A GLANCE

⏱ Time:O(n + m)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem is a classic application of the sliding window technique combined with a fixed-size character frequency table. By maintaining a window of length equal to the key string over the message, we can compare the multiset of characters inside the window to that of the key in O(1) time per shift, because the alphabet size is constant (e.g., 26 lowercase letters or 128 ASCII). Naïve solutions that generate every permutation of the key or compare each substring from scratch incur O(m·n) time (where m = |key|, n = |message|) and quickly become infeasible for large inputs. The optimal paradigm treats the problem as a “find an anagram” task: we pre‑compute the frequency count of the key, then slide a window across the message, updating the counts incrementally—adding the incoming character and removing the outgoing one. When the window’s count matches the key’s count, we have found a valid permutation. This yields linear time because each character is processed a constant number of times, and constant extra space because the frequency table size does not depend on input length.

Interview Questions on This Problem

Q1How would you modify the sliding‑window solution to support Unicode characters beyond the ASCII range while still keeping O(1) extra space?

Use a hash map (e.g., unordered_map<char32_t,int>) to store frequencies; the space becomes O(k) where k is the number of distinct characters in the key, which is bounded by the key length and typically small, preserving near‑constant extra space for practical inputs.

Q2Explain why checking equality of two frequency tables after each window shift can be done in O(1) time instead of O(AlphabetSize).

Maintain a mismatch counter that tracks how many characters have differing counts; when a character’s count is adjusted, update the counter accordingly. The window matches the key when the counter reaches zero, eliminating the need to scan the entire table each time.

Q3In a distributed log‑processing system, how could you detect a permutation of a short pattern across a massive stream without storing the entire stream?

Apply the same sliding‑window logic on the streaming data: keep only the current window’s character counts and the mismatch counter. Since each log entry is processed once and the window size is fixed, memory usage stays constant regardless of stream length.

Examples

Example 1

Input

{ "key": "abc", "message": "abdcba" }

Output

true

Explanation: The length of the key is 3, so we examine every window of size 3 in the message: - Window "abd" → frequencies {a:1,b:1,d:1} ≠ {a:1,b:1,c:1} - Window "bdc" → {b:1,d:1,c:1} ≠ target - Window "dcb" → {d:1,c:1,b:1} ≠ target - Window "cba" → {c:1,b:1,a:1} matches the key's frequency map exactly. Hence a permutation of the key exists, and the answer is true.

Example 2

Input

{ "key": "aab", "message": "xyzab" }

Output

false

Explanation: Key length = 3. Sliding windows of size 3 in the message are: - "xyz" → {x:1,y:1,z:1} - "yza" → {y:1,z:1,a:1} - "zab" → {z:1,a:1,b:1} None of these windows contain two 'a's and one 'b', which is the required multiset for the key. Therefore no permutation is present and the result is false.

Example 3

Input

{ "key": "aa", "message": "aaaa" }

Output

true

Explanation: Key length = 2. Every length‑2 window in the message is "aa". The frequency map of each window is {a:2}, identical to the key's map. The first window already satisfies the condition, so the function returns true.

Constraints

1 <= key.length <= 10^5
1 <= message.length <= 10^5
key.length <= message.length
key and message consist only of lowercase English letters ('a'–'z')

Optimal Approach & Strategy

Use a sliding window of length m with a fixed-size frequency table, updating counts incrementally and comparing via a mismatch counter for O(n) time and O(1) space.

Brute Force Approach

Generate every permutation of the key (m! possibilities) and check each one against every substring of the message, leading to exponential time.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n + m)

/**
 * @param {string} key
 * @param {string} message
 * @return {boolean}
 */
var checkInclusion = function(key, message) {
    const n = key.length;
    const m = message.length;
    if (n > m) return false;
    
    const keyCount = new Array(26).fill(0);
    const windowCount = new Array(26).fill(0);
    
    for (let i = 0; i < n; i++) {
        keyCount[key.charCodeAt(i) - 97]++;
        windowCount[message.charCodeAt(i) - 97]++;
    }
    
    if (keyCount.join(',') === windowCount.join(',')) return true;
    
    for (let i = n; i < m; i++) {
        windowCount[message.charCodeAt(i) - 97]++;
        windowCount[message.charCodeAt(i - n) - 97]--;
        if (keyCount.join(',') === windowCount.join(',')) return true;
    }
    
    return false;
};

class Solution {
public:
    bool checkInclusion(string key, string message) {
        int n = key.size();
        int m = message.size();
        if (n > m) return false;
        
        vector<int> keyCount(26, 0);
        vector<int> windowCount(26, 0);
        
        for (int i = 0; i < n; i++) {
            keyCount[key[i] - 'a']++;
            windowCount[message[i] - 'a']++;
        }
        
        if (keyCount == windowCount) return true;
        
        for (int i = n; i < m; i++) {
            windowCount[message[i] - 'a']++;
            windowCount[message[i - n] - 'a']--;
            if (keyCount == windowCount) return true;
        }
        
        return false;
    }
};

class Solution {
    public boolean checkInclusion(String key, String message) {
        int n = key.length();
        int m = message.length();
        if (n > m) return false;
        
        int[] keyCount = new int[26];
        int[] windowCount = new int[26];
        
        for (int i = 0; i < n; i++) {
            keyCount[key.charAt(i) - 'a']++;
            windowCount[message.charAt(i) - 'a']++;
        }
        
        if (Arrays.equals(keyCount, windowCount)) return true;
        
        for (int i = n; i < m; i++) {
            windowCount[message.charAt(i) - 'a']++;
            windowCount[message.charAt(i - n) - 'a']--;
            if (Arrays.equals(keyCount, windowCount)) return true;
        }
        
        return false;
    }
}

class Solution:
    def checkInclusion(self, key: str, message: str) -> bool:
        n, m = len(key), len(message)
        if n > m:
            return False
        
        key_count = [0] * 26
        window_count = [0] * 26
        
        for i in range(n):
            key_count[ord(key[i]) - ord('a')] += 1
            window_count[ord(message[i]) - ord('a')] += 1
        
        if key_count == window_count:
            return True
        
        for i in range(n, m):
            window_count[ord(message[i]) - ord('a')] += 1
            window_count[ord(message[i - n]) - ord('a')] -= 1
            if key_count == window_count:
                return True
        
        return False

/**
 * @param {string} key
 * @param {string} message
 * @return {boolean}
 */
var checkInclusion = function(key, message) {
    const n = key.length;
    const m = message.length;
    if (n > m) return false;
    
    const keyCount = new Array(26).fill(0);
    const windowCount = new Array(26).fill(0);
    
    for (let i = 0; i < n; i++) {
        keyCount[key.charCodeAt(i) - 97]++;
        windowCount[message.charCodeAt(i) - 97]++;
    }
    
    if (keyCount.join(',') === windowCount.join(',')) return true;
    
    for (let i = n; i < m; i++) {
        windowCount[message.charCodeAt(i) - 97]++;
        windowCount[message.charCodeAt(i - n) - 97]--;
        if (keyCount.join(',') === windowCount.join(',')) return true;
    }
    
    return false;
};

Asked in Top Tech Interviews

Adobe

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Permutation Inclusion Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Sliding Window

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Permutation Inclusion — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor