Permutation in String

🎯

Permutation in String

mediumSLIDING_WINDOWAmazonMicrosoft

Imagine you want to quickly check if a scrambled password is hidden inside a longer text without rearranging the text itself.

💡 This problem is about checking if one string contains any permutation of another string as a substring. Beginners often struggle because they try to generate all permutations explicitly, which is inefficient. Instead, understanding how to use frequency counts and sliding windows is key.

📋

Problem Statement

Given two strings s1 and s2, return true if s2 contains a permutation of s1. In other words, one of s1's permutations is the substring of s2. Otherwise, return false.

1 ≤ s1.length, s2.length ≤ 10^5s1 and s2 consist of lowercase English letters only

💡

Example

Input"s1 = \"ab\", s2 = \"eidbaooo\""

Outputtrue

s2 contains "ba", which is a permutation of s1.

Input"s1 = \"ab\", s2 = \"eidboaoo\""

Outputfalse

No permutation of s1 is a substring of s2.

• s1 longer than s2 → false
• s1 and s2 are identical → true
• s1 or s2 is a single character → true if s2 contains s1
• s2 contains multiple permutations of s1 → true

⚠️

Common Mistakes

Not removing characters leaving the window correctly

Window frequency counts become incorrect, causing false positives or negatives

✅ Always decrement frequency of the character leaving the window and handle zero counts properly

Comparing frequency maps inefficiently every step

Leads to timeouts on large inputs

✅ Use a match count to track how many characters match frequencies exactly

Not handling zero counts in frequency maps

Frequency maps appear different even when logically equal, causing wrong results

✅ Remove keys with zero count or use fixed-size arrays for direct comparison

Not checking if s1 length is greater than s2 upfront

Unnecessary computation or index errors

✅ Return false immediately if s1 is longer than s2

🧠

Brute Force (Check All Substrings)

💡 This approach exists to build intuition by directly checking every substring of s2 that matches s1's length to see if it's a permutation. It is simple but inefficient, highlighting why optimization is needed.

Intuition

Check every substring of s2 with length equal to s1 and verify if it is a permutation by comparing character counts.

Algorithm

1. For each substring of s2 with length equal to s1:
2. Count the frequency of characters in this substring.
3. Count the frequency of characters in s1.
4. Compare the two frequency maps; if equal, return true.
5. If no substring matches, return false.

💡 The difficulty is in realizing that checking all substrings is straightforward but costly, and frequency comparison is the key to checking permutations.

</>

Code

def checkInclusion(s1: str, s2: str) -> bool:
    from collections import Counter
    len_s1 = len(s1)
    len_s2 = len(s2)
    s1_count = Counter(s1)
    for i in range(len_s2 - len_s1 + 1):
        window = s2[i:i+len_s1]
        window_count = Counter(window)
        if window_count == s1_count:
            return True
    return False

# Driver code
if __name__ == "__main__":
    print(checkInclusion("ab", "eidbaooo"))  # True
    print(checkInclusion("ab", "eidboaoo"))  # False

Line Notes

from collections import CounterImport Counter to easily count character frequencies.

len_s1 = len(s1)Store length of s1 for window size.

s1_count = Counter(s1)Precompute frequency of s1 once to compare against.

for i in range(len_s2 - len_s1 + 1)Iterate over all possible substrings of s2 with length equal to s1.

window_count = Counter(window)Count frequency of current substring to compare with s1_count.

if window_count == s1_countCheck if current substring is a permutation of s1.

import java.util.*;

public class Solution {
    public static boolean checkInclusion(String s1, String s2) {
        int lenS1 = s1.length(), lenS2 = s2.length();
        if (lenS1 > lenS2) return false;
        int[] s1Count = new int[26];
        for (char c : s1.toCharArray()) s1Count[c - 'a']++;
        for (int i = 0; i <= lenS2 - lenS1; i++) {
            int[] windowCount = new int[26];
            for (int j = i; j < i + lenS1; j++) {
                windowCount[s2.charAt(j) - 'a']++;
            }
            if (Arrays.equals(s1Count, windowCount)) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(checkInclusion("ab", "eidbaooo")); // true
        System.out.println(checkInclusion("ab", "eidboaoo")); // false
    }
}

Line Notes

int lenS1 = s1.length(), lenS2 = s2.length();Store lengths of s1 and s2 for iteration limits.

int[] s1Count = new int[26];Frequency array for s1 characters to compare against.

for (int i = 0; i <= lenS2 - lenS1; i++)Loop over all substrings of s2 with length s1.

int[] windowCount = new int[26];Frequency array for current substring of s2.

if (Arrays.equals(s1Count, windowCount))Check if current substring is a permutation of s1.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool checkInclusion(string s1, string s2) {
    int lenS1 = s1.size(), lenS2 = s2.size();
    if (lenS1 > lenS2) return false;
    vector<int> s1Count(26, 0);
    for (char c : s1) s1Count[c - 'a']++;
    for (int i = 0; i <= lenS2 - lenS1; i++) {
        vector<int> windowCount(26, 0);
        for (int j = i; j < i + lenS1; j++) {
            windowCount[s2[j] - 'a']++;
        }
        if (s1Count == windowCount) return true;
    }
    return false;
}

int main() {
    cout << boolalpha << checkInclusion("ab", "eidbaooo") << endl; // true
    cout << boolalpha << checkInclusion("ab", "eidboaoo") << endl; // false
    return 0;
}

Line Notes

int lenS1 = s1.size(), lenS2 = s2.size();Store lengths of s1 and s2 for iteration limits.

vector<int> s1Count(26, 0);Initialize frequency vector for s1 characters.

for (int i = 0; i <= lenS2 - lenS1; i++)Iterate over all substrings of s2 with length s1.

vector<int> windowCount(26, 0);Frequency vector for current substring of s2.

if (s1Count == windowCount)Compare frequency vectors to check for permutation.

function checkInclusion(s1, s2) {
    const lenS1 = s1.length, lenS2 = s2.length;
    if (lenS1 > lenS2) return false;
    const s1Count = Array(26).fill(0);
    for (const c of s1) s1Count[c.charCodeAt(0) - 97]++;
    for (let i = 0; i <= lenS2 - lenS1; i++) {
        const windowCount = Array(26).fill(0);
        for (let j = i; j < i + lenS1; j++) {
            windowCount[s2.charCodeAt(j) - 97]++;
        }
        if (s1Count.every((val, idx) => val === windowCount[idx])) return true;
    }
    return false;
}

// Test cases
console.log(checkInclusion("ab", "eidbaooo")); // true
console.log(checkInclusion("ab", "eidboaoo")); // false

Line Notes

const lenS1 = s1.length, lenS2 = s2.length;Store lengths of s1 and s2 for iteration limits.

const s1Count = Array(26).fill(0);Create frequency array for s1 characters.

for (let i = 0; i <= lenS2 - lenS1; i++)Loop over all substrings of s2 with length s1.

const windowCount = Array(26).fill(0);Frequency array for current substring of s2.

if (s1Count.every((val, idx) => val === windowCount[idx]))Check if current substring matches s1 frequency.

⏱

Complexity

TimeO((n - m + 1) * m) where n = len(s2), m = len(s1)

SpaceO(m) for frequency maps

For each of the n-m+1 substrings, we count frequencies in O(m) time, leading to O(n*m) overall.

💡 For n=1000 and m=10, this means about 10,000 operations, which is slow for large inputs.

Interview Verdict: TLE for large inputs

This approach is too slow for big strings but helps understand the problem and why optimization is needed.

🧠

Sliding Window with Frequency Map Comparison

💡 This approach improves efficiency by using a sliding window and updating frequency counts incrementally instead of recounting each substring from scratch.

Intuition

Use a fixed-size sliding window over s2, maintain a frequency map of the current window, and compare it to s1's frequency map to detect permutations.

Algorithm

1. Compute frequency map of s1.
2. Initialize a sliding window of size equal to s1's length on s2.
3. Maintain frequency map of current window.
4. Slide the window by one character at a time, updating counts incrementally.
5. After each slide, compare frequency maps; if equal, return true.
6. If no match found, return false.

💡 The key challenge is updating counts efficiently and comparing frequency maps without recomputing from scratch.

</>

Code

def checkInclusion(s1: str, s2: str) -> bool:
    from collections import Counter
    len_s1, len_s2 = len(s1), len(s2)
    if len_s1 > len_s2:
        return False
    s1_count = Counter(s1)
    window_count = Counter(s2[:len_s1])
    if window_count == s1_count:
        return True
    for i in range(len_s1, len_s2):
        start_char = s2[i - len_s1]
        window_count[start_char] -= 1
        if window_count[start_char] == 0:
            del window_count[start_char]
        window_count[s2[i]] += 1
        if window_count == s1_count:
            return True
    return False

# Driver code
if __name__ == "__main__":
    print(checkInclusion("ab", "eidbaooo"))  # True
    print(checkInclusion("ab", "eidboaoo"))  # False

Line Notes

len_s1, len_s2 = len(s1), len(s2)Store lengths of s1 and s2 for window size and iteration.

if len_s1 > len_s2: return FalseIf s1 is longer, no permutation possible.

s1_count = Counter(s1)Frequency map of s1 characters.

window_count = Counter(s2[:len_s1])Initialize frequency map for the first window.

if window_count == s1_countCheck if current window is a permutation.

window_count[start_char] -= 1Remove count of the char leaving the window.

if window_count[start_char] == 0: del window_count[start_char]Clean up zero counts to keep comparison accurate.

window_count[s2[i]] += 1Add count of new char entering the window.

import java.util.*;

public class Solution {
    public static boolean checkInclusion(String s1, String s2) {
        int lenS1 = s1.length(), lenS2 = s2.length();
        if (lenS1 > lenS2) return false;
        int[] s1Count = new int[26];
        int[] windowCount = new int[26];
        for (int i = 0; i < lenS1; i++) {
            s1Count[s1.charAt(i) - 'a']++;
            windowCount[s2.charAt(i) - 'a']++;
        }
        if (Arrays.equals(s1Count, windowCount)) return true;
        for (int i = lenS1; i < lenS2; i++) {
            windowCount[s2.charAt(i) - 'a']++;
            windowCount[s2.charAt(i - lenS1) - 'a']--;
            if (Arrays.equals(s1Count, windowCount)) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(checkInclusion("ab", "eidbaooo")); // true
        System.out.println(checkInclusion("ab", "eidboaoo")); // false
    }
}

Line Notes

int lenS1 = s1.length(), lenS2 = s2.length();Store lengths of s1 and s2 for window size and iteration.

if (lenS1 > lenS2) return false;If s1 is longer, no permutation possible.

int[] s1Count = new int[26];Frequency array for s1 characters.

int[] windowCount = new int[26];Frequency array for current window in s2.

for (int i = 0; i < lenS1; i++)Initialize frequency arrays for s1 and first window.

if (Arrays.equals(s1Count, windowCount))Check if current window is a permutation.

windowCount[s2.charAt(i) - 'a']++Add new character entering the window.

windowCount[s2.charAt(i - lenS1) - 'a']--Remove character leaving the window.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool checkInclusion(string s1, string s2) {
    int lenS1 = s1.size(), lenS2 = s2.size();
    if (lenS1 > lenS2) return false;
    vector<int> s1Count(26, 0), windowCount(26, 0);
    for (int i = 0; i < lenS1; i++) {
        s1Count[s1[i] - 'a']++;
        windowCount[s2[i] - 'a']++;
    }
    if (s1Count == windowCount) return true;
    for (int i = lenS1; i < lenS2; i++) {
        windowCount[s2[i] - 'a']++;
        windowCount[s2[i - lenS1] - 'a']--;
        if (s1Count == windowCount) return true;
    }
    return false;
}

int main() {
    cout << boolalpha << checkInclusion("ab", "eidbaooo") << endl; // true
    cout << boolalpha << checkInclusion("ab", "eidboaoo") << endl; // false
    return 0;
}

Line Notes

int lenS1 = s1.size(), lenS2 = s2.size();Store lengths of s1 and s2 for window size and iteration.

if (lenS1 > lenS2) return false;If s1 is longer, no permutation possible.

vector<int> s1Count(26, 0), windowCount(26, 0);Frequency vectors for s1 and current window.

for (int i = 0; i < lenS1; i++)Initialize frequency vectors for s1 and first window.

if (s1Count == windowCount) return true;Compare frequency vectors to detect permutation.

windowCount[s2[i] - 'a']++;Add new character frequency as window slides.

windowCount[s2[i - lenS1] - 'a']--;Remove frequency of character leaving window.

function checkInclusion(s1, s2) {
    const lenS1 = s1.length, lenS2 = s2.length;
    if (lenS1 > lenS2) return false;
    const s1Count = Array(26).fill(0);
    const windowCount = Array(26).fill(0);
    for (let i = 0; i < lenS1; i++) {
        s1Count[s1.charCodeAt(i) - 97]++;
        windowCount[s2.charCodeAt(i) - 97]++;
    }
    if (s1Count.every((val, idx) => val === windowCount[idx])) return true;
    for (let i = lenS1; i < lenS2; i++) {
        windowCount[s2.charCodeAt(i) - 97]++;
        windowCount[s2.charCodeAt(i - lenS1) - 97]--;
        if (s1Count.every((val, idx) => val === windowCount[idx])) return true;
    }
    return false;
}

// Test cases
console.log(checkInclusion("ab", "eidbaooo")); // true
console.log(checkInclusion("ab", "eidboaoo")); // false

Line Notes

const lenS1 = s1.length, lenS2 = s2.length;Store lengths of s1 and s2 for window size and iteration.

if (lenS1 > lenS2) return false;If s1 is longer, no permutation possible.

const s1Count = Array(26).fill(0);Frequency array for s1 characters.

const windowCount = Array(26).fill(0);Frequency array for current window in s2.

for (let i = 0; i < lenS1; i++)Initialize frequency arrays for s1 and first window.

if (s1Count.every((val, idx) => val === windowCount[idx]))Check if current window matches s1 frequency.

windowCount[s2.charCodeAt(i) - 97]++;Add frequency of new character entering window.

windowCount[s2.charCodeAt(i - lenS1) - 97]--;Remove frequency of character leaving window.

⏱

Complexity

TimeO(n) where n = len(s2)

SpaceO(1) since frequency arrays are fixed size (26 letters)

We slide the window once over s2, updating counts in constant time and comparing fixed-size arrays.

💡 For n=100000, this means about 100000 operations, which is efficient for large inputs.

Interview Verdict: Accepted

This approach is efficient and practical for interviews, demonstrating mastery of sliding window technique.

🧠

Sliding Window with Match Count Optimization

💡 This approach further optimizes by avoiding full frequency array comparisons on every step, instead tracking how many characters currently match the required frequency.

Intuition

Maintain a count of how many characters have the exact required frequency in the current window. When this count equals the number of unique characters in s1, we have a valid permutation.

Algorithm

1. Count frequency of characters in s1 and track number of unique characters.
2. Initialize sliding window frequency counts and a match count.
3. Expand window by adding characters and update match count when frequencies match.
4. Shrink window by removing characters and update match count accordingly.
5. If match count equals unique character count, return true.
6. Return false if no valid window found.

💡 The challenge is carefully updating match count to reflect exact frequency matches without full array comparisons.

</>

Code

def checkInclusion(s1: str, s2: str) -> bool:
    len_s1, len_s2 = len(s1), len(s2)
    if len_s1 > len_s2:
        return False
    count = [0] * 26
    for c in s1:
        count[ord(c) - ord('a')] += 1
    left = 0
    right = 0
    required = sum(1 for x in count if x > 0)
    formed = 0
    window_count = [0] * 26
    while right < len_s2:
        idx = ord(s2[right]) - ord('a')
        window_count[idx] += 1
        if window_count[idx] == count[idx]:
            formed += 1
        if right - left + 1 > len_s1:
            left_idx = ord(s2[left]) - ord('a')
            if window_count[left_idx] == count[left_idx]:
                formed -= 1
            window_count[left_idx] -= 1
            left += 1
        if formed == required:
            return True
        right += 1
    return False

# Driver code
if __name__ == "__main__":
    print(checkInclusion("ab", "eidbaooo"))  # True
    print(checkInclusion("ab", "eidboaoo"))  # False

Line Notes

count = [0] * 26Frequency array for s1 characters.

required = sum(1 for x in count if x > 0)Count how many unique characters need to match.

window_count = [0] * 26Frequency array for current window in s2.

while right < len_s2:Expand window by moving right pointer.

window_count[idx] += 1Add frequency of new character entering window.

if window_count[idx] == count[idx]: formed += 1Increment formed when a character frequency matches exactly.

if right - left + 1 > len_s1:Shrink window if it exceeds s1 length.

if window_count[left_idx] == count[left_idx]: formed -= 1Decrement formed when frequency no longer matches before removing character.

window_count[left_idx] -= 1Remove frequency of character leaving window.

left += 1Move left pointer to shrink window.

if formed == required: return TrueIf all characters match required frequency, return true.

public class Solution {
    public static boolean checkInclusion(String s1, String s2) {
        int lenS1 = s1.length(), lenS2 = s2.length();
        if (lenS1 > lenS2) return false;
        int[] count = new int[26];
        for (char c : s1.toCharArray()) count[c - 'a']++;
        int required = 0;
        for (int c : count) if (c > 0) required++;
        int[] windowCount = new int[26];
        int formed = 0, left = 0, right = 0;
        while (right < lenS2) {
            int idx = s2.charAt(right) - 'a';
            windowCount[idx]++;
            if (windowCount[idx] == count[idx]) formed++;
            if (right - left + 1 > lenS1) {
                int leftIdx = s2.charAt(left) - 'a';
                if (windowCount[leftIdx] == count[leftIdx]) formed--;
                windowCount[leftIdx]--;
                left++;
            }
            if (formed == required) return true;
            right++;
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(checkInclusion("ab", "eidbaooo")); // true
        System.out.println(checkInclusion("ab", "eidboaoo")); // false
    }
}

Line Notes

int[] count = new int[26];Frequency array for s1 characters.

int required = 0; for (int c : count) if (c > 0) required++;Count unique characters to match.

int[] windowCount = new int[26];Frequency array for current window in s2.

while (right < lenS2)Expand window by moving right pointer.

windowCount[idx]++;Add frequency of new character entering window.

if (windowCount[idx] == count[idx]) formed++;Increment formed when frequency matches exactly.

if (right - left + 1 > lenS1)Maintain window size equal to s1 length.

if (windowCount[leftIdx] == count[leftIdx]) formed--;Decrement formed when frequency no longer matches before removing character.

windowCount[leftIdx]--;Remove frequency of character leaving window.

left++;Move left pointer to shrink window.

if (formed == required) return true;If all characters match required frequency, return true.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool checkInclusion(string s1, string s2) {
    int lenS1 = s1.size(), lenS2 = s2.size();
    if (lenS1 > lenS2) return false;
    vector<int> count(26, 0), windowCount(26, 0);
    for (char c : s1) count[c - 'a']++;
    int required = 0;
    for (int c : count) if (c > 0) required++;
    int formed = 0, left = 0, right = 0;
    while (right < lenS2) {
        int idx = s2[right] - 'a';
        windowCount[idx]++;
        if (windowCount[idx] == count[idx]) formed++;
        if (right - left + 1 > lenS1) {
            int leftIdx = s2[left] - 'a';
            if (windowCount[leftIdx] == count[leftIdx]) formed--;
            windowCount[leftIdx]--;
            left++;
        }
        if (formed == required) return true;
        right++;
    }
    return false;
}

int main() {
    cout << boolalpha << checkInclusion("ab", "eidbaooo") << endl; // true
    cout << boolalpha << checkInclusion("ab", "eidboaoo") << endl; // false
    return 0;
}

Line Notes

vector<int> count(26, 0), windowCount(26, 0);Frequency vectors for s1 and current window.

int required = 0; for (int c : count) if (c > 0) required++;Count unique characters to match.

int formed = 0, left = 0, right = 0;Initialize pointers and formed count.

while (right < lenS2)Expand window by moving right pointer.

windowCount[idx]++;Add frequency of new character entering window.

if (windowCount[idx] == count[idx]) formed++;Increment formed when frequency matches exactly.

if (right - left + 1 > lenS1)Keep window size fixed to s1 length.

if (windowCount[leftIdx] == count[leftIdx]) formed--;Decrement formed when frequency no longer matches before removing character.

windowCount[leftIdx]--;Remove frequency of character leaving window.

left++;Move left pointer to shrink window.

if (formed == required) return true;If all characters match required frequency, return true.

function checkInclusion(s1, s2) {
    const lenS1 = s1.length, lenS2 = s2.length;
    if (lenS1 > lenS2) return false;
    const count = Array(26).fill(0);
    for (const c of s1) count[c.charCodeAt(0) - 97]++;
    let required = count.filter(x => x > 0).length;
    const windowCount = Array(26).fill(0);
    let formed = 0, left = 0, right = 0;
    while (right < lenS2) {
        let idx = s2.charCodeAt(right) - 97;
        windowCount[idx]++;
        if (windowCount[idx] === count[idx]) formed++;
        if (right - left + 1 > lenS1) {
            let leftIdx = s2.charCodeAt(left) - 97;
            if (windowCount[leftIdx] === count[leftIdx]) formed--;
            windowCount[leftIdx]--;
            left++;
        }
        if (formed === required) return true;
        right++;
    }
    return false;
}

// Test cases
console.log(checkInclusion("ab", "eidbaooo")); // true
console.log(checkInclusion("ab", "eidboaoo")); // false

Line Notes

const count = Array(26).fill(0);Frequency array for s1 characters.

let required = count.filter(x => x > 0).length;Count unique characters to match.

const windowCount = Array(26).fill(0);Frequency array for current window in s2.

let formed = 0, left = 0, right = 0;Initialize pointers and formed count.

while (right < lenS2)Expand window by moving right pointer.

windowCount[idx]++;Add frequency of new character entering window.

if (windowCount[idx] === count[idx]) formed++;Increment formed when frequency matches exactly.

if (right - left + 1 > lenS1)Maintain window size equal to s1 length.

if (windowCount[leftIdx] === count[leftIdx]) formed--;Decrement formed when frequency no longer matches before removing character.

windowCount[leftIdx]--;Remove frequency of character leaving window.

left++;Move left pointer to shrink window.

if (formed === required) return true;If all characters match required frequency, return true.

⏱

Complexity

TimeO(n) where n = len(s2)

SpaceO(1) fixed size arrays for frequency counts

Each character is processed once, and match count updates are constant time, avoiding full array comparisons.

💡 This approach is the most efficient and elegant for large inputs.

Interview Verdict: Accepted

This is the optimal approach to implement in interviews for this problem.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, coding the sliding window with match count optimization is best for efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n*m)	O(m)	No	N/A	Mention only - never code due to inefficiency
2. Sliding Window with Frequency Map Comparison	O(n)	O(1)	No	N/A	Good for initial optimization, acceptable to code
3. Sliding Window with Match Count Optimization	O(n)	O(1)	No	N/A	Optimal approach to code in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem constraints and examples.Step 2: Describe brute force approach and its inefficiency.Step 3: Introduce sliding window with frequency maps.Step 4: Optimize with match count to avoid full comparisons.Step 5: Code the optimal solution and test edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Ability to identify sliding window pattern, optimize frequency comparisons, and write clean, bug-free code.

Common Follow-ups

• What if s1 and s2 contain uppercase letters? → Adjust frequency arrays to handle full ASCII or Unicode.
• Can you find all starting indices of permutations? → Modify to collect indices instead of returning boolean.

💡 These follow-ups test adaptability and deeper understanding of the sliding window technique.

🔍

Pattern Recognition

When to Use

1) Problem asks if a string contains a permutation of another; 2) Fixed substring length equal to s1; 3) Need to check character frequency matches; 4) Sliding window can be applied.

Signature Phrases

contains a permutationsubstring of s2frequency of characters

NOT This Pattern When

Problems requiring subsequence checks or variable window sizes without fixed length are different patterns.

Similar Problems

Find All Anagrams in a String - find all indices instead of booleanMinimum Window Substring - variable window size with frequency constraints

Practice

1. You are given an integer array and a fixed window size k. The task is to find the contiguous subarray of length k that has the maximum average value. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Sliding window technique maintaining a running sum of the current window

B. Brute force nested loops checking all subarrays of size k

C. Dynamic programming with memoization of subproblems

D. Greedy approach selecting the largest elements regardless of position

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the maximum average of any contiguous subarray of fixed size k, which suggests examining all windows of size k.

2. Step 2: Identify optimal approach

   Sliding window maintains a running sum by adding the new element and removing the oldest, achieving O(n) time. Brute force is O(n*k), DP and greedy do not fit this fixed-size window problem optimally.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sliding window updates sum in O(1) per step, total O(n) time [OK]

Hint: Sliding window updates sum in O(1) per step [OK]

Common Mistakes:

• Thinking greedy works without considering window contiguity
• Assuming DP is needed for fixed-size windows

2. What is the time complexity of the sliding window solution for finding the maximum average subarray of size k in an array of length n, and why might some candidates mistakenly think it is higher?

medium

A. O(n) because each element is added and removed exactly once from the window sum

B. O(n*k) because each window sum is recomputed from scratch

C. O(n log k) due to sorting elements within each window

D. O(k) because the window size dominates the computation

Solution

1. Step 1: Analyze loop operations

   The sliding window sums are updated by adding one new element and removing one old element per iteration, so each element is processed twice.

2. Step 2: Identify complexity

   Since the loop runs n-k times and each iteration is O(1), total time is O(n). The common mistake is thinking sum is recomputed fully each time, which is O(n*k).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sliding window updates sum in constant time per iteration [OK]

Hint: Sliding window updates sum in O(1) per iteration [OK]

Common Mistakes:

• Assuming sum recomputed fully each window
• Confusing window size k with input size n

3. What is the time complexity of the optimized sliding window algorithm that uses filtered characters for the minimum window substring problem, where n is the length of s and m is the length of t?

medium

A. O(n) because each character in s is visited at most twice by the two pointers

B. O(n * m) because for each character in s we check all characters in t

C. O(n + m) because we filter s and then slide over filtered characters

D. O(n^2) because shrinking and expanding the window can cause nested loops

Solution

1. Step 1: Identify main loops

   The algorithm uses two pointers moving over filtered characters, each pointer advances at most n times.

2. Step 2: Analyze filtering and counting

   Filtering s takes O(n), sliding window over filtered characters is O(n) since each character is visited twice max.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer sliding window is linear time [OK]

Hint: Two pointers each move forward at most n times [OK]

Common Mistakes:

• Confusing filtering cost
• Assuming nested loops cause O(n^2)
• Ignoring that each pointer moves only forward

4. Suppose the input array can contain negative numbers as well as 0s and 1s. Which of the following statements about using the two-pointer sliding window approach to count subarrays with sum equal to goal is correct?

hard

A. Using prefix sums with a hash map is no longer valid when negative numbers are present.

B. The two-pointer sliding window approach still works correctly with minor modifications to handle negative numbers.

C. The two-pointer sliding window approach fails because the window sum can decrease unpredictably, causing infinite loops or incorrect counts.

D. Brute force is the only correct approach when negative numbers are allowed.

Solution

1. Step 1: Understand sliding window assumptions

   Sliding window relies on the sum increasing when expanding right pointer and decreasing when moving left pointer, which holds for non-negative numbers.

2. Step 2: Effect of negative numbers

   Negative numbers can cause sum to decrease when expanding right pointer, breaking monotonicity and causing infinite loops or incorrect counts.

3. Step 3: Alternative approaches

   Prefix sums with hash map still work with negatives; brute force is correct but inefficient.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Sliding window fails with negative numbers due to non-monotonic sum [OK]

Hint: Sliding window requires non-negative elements for monotonic sum [OK]

Common Mistakes:

• Assuming sliding window works unchanged with negatives
• Thinking prefix sums with hash map fail with negatives
• Believing brute force is the only solution

5. Suppose the fruits problem is modified so that you can pick fruits from trees non-contiguously but still want to maximize the total number of fruits collected with at most two fruit types. Which approach correctly solves this variant?

hard

A. Count total occurrences of each fruit type and sum the two largest counts

B. Sort fruits and use two pointers to find longest contiguous segment with two types

C. Use dynamic programming to find longest subsequence with at most two distinct fruits

D. Use the same sliding window approach since it handles at most two fruit types

Solution

1. Step 1: Understand non-contiguous picking

   Since picking is non-contiguous, order does not matter; we want max total fruits of two types.

2. Step 2: Optimal solution is sum of two largest fruit counts

   Count frequency of each fruit type, pick top two counts, sum them for max fruits.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Non-contiguous means subsequence, so frequency sums suffice [OK]

Hint: Non-contiguous -> sum top two fruit counts [OK]

Common Mistakes:

• Applying sliding window to non-contiguous
• Using DP unnecessarily
• Sorting loses subsequence property