Permutation in String

📋

Permutation in String

Edge cases:

</>

IDE

def checkInclusion(s1: str, s2: str) -> bool:public boolean checkInclusion(String s1, String s2)bool checkInclusion(string s1, string s2)function checkInclusion(s1, s2)

def checkInclusion(s1, s2):
    # Write your solution here
    pass

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        // Write your solution here
        return false;
    }
}

#include <string>
using namespace std;

bool checkInclusion(string s1, string s2) {
    // Write your solution here
    return false;
}

function checkInclusion(s1, s2) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: trueGreedy partial matching: returning true if some chars match but not full frequency equality.✅ Compare full frequency maps for each window, not just presence of characters.

Wrong: falseIgnoring repeated characters or treating duplicates as unique, causing missed matches.✅ Count frequencies of all characters precisely and compare frequency maps exactly.

Wrong: trueReturning true when s1 is longer than s2 without length check.✅ Add a length check at start: if len(s1) > len(s2) return false.

Wrong: falseNot checking for exact equality when s1 equals s2.✅ Add direct equality check before sliding window logic.

Wrong: TLEUsing brute force O(n*m) approach on large inputs.✅ Implement O(n) sliding window with frequency arrays to avoid recomputation.

✓

Test Cases

Focus on handling boundary cases like empty strings and length mismatches.

Watch out for subtle bugs like repeated characters and greedy matching traps.

Optimize your solution to linear time using sliding window and frequency arrays.

t1_01basic

Input{"s1":"ab","s2":"eidbaooo"}

Expectedtrue

⏱ Performance - must finish in 2000ms

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

💡 Try sliding a window of length s1 over s2 and compare character counts.

💡 Use frequency maps to check if the current window matches s1's character counts.

💡 Maintain a sliding window frequency and compare it to s1's frequency to find a match.

Why it failed: Returned false but s2 contains a permutation of s1. Fix by correctly comparing frequency maps for each window.

✓ Correctly identified that s2 contains a permutation of s1.

t1_02basic

Input{"s1":"abc","s2":"ccccbbbbaaaa"}

Expectedfalse

⏱ Performance - must finish in 2000ms

s2 does not contain any permutation of s1 as substring.

💡 Check all substrings of length equal to s1 in s2 for matching frequency.

💡 If no window matches s1's frequency map, return false.

💡 Ensure the sliding window moves correctly and frequency counts update properly.

Why it failed: Returned true incorrectly; no substring of s2 is a permutation of s1. Fix by verifying frequency counts exactly.

✓ Correctly identified that s2 does not contain any permutation of s1.

t2_01edge

Input{"s1":"abc","s2":"ab"}

Expectedfalse

⏱ Performance - must finish in 2000ms

s1 is longer than s2, so s2 cannot contain any permutation of s1.

💡 Check if s1's length is greater than s2's length before processing.

💡 If s1 is longer, immediately return false without further checks.

💡 Add a length check at the start to handle this boundary case.

Why it failed: Returned true when s1 is longer than s2. Fix by adding a length check: if len(s1) > len(s2) return false.

✓ Correctly handled the case where s1 is longer than s2.

t2_02edge

Input{"s1":"a","s2":"a"}

Expectedtrue

⏱ Performance - must finish in 2000ms

Both s1 and s2 are single characters and identical, so s2 contains a permutation of s1.

💡 Single character strings are trivial permutations if characters match.

💡 Check if s1 is a substring of s2 when lengths are 1.

💡 Return true if s1 equals s2 for single character inputs.

Why it failed: Returned false for identical single-character strings. Fix by handling single-character equality correctly.

✓ Correctly identified permutation for single-character identical strings.

t2_03edge

Input{"s1":"abc","s2":"abc"}

Expectedtrue

⏱ Performance - must finish in 2000ms

s1 and s2 are identical, so s2 contains a permutation of s1 (itself).

💡 If s1 equals s2, return true immediately.

💡 Check for exact string equality as a quick shortcut.

💡 This avoids unnecessary sliding window checks.

Why it failed: Returned false when s1 equals s2. Fix by adding a direct equality check before sliding window.

✓ Correctly handled identical s1 and s2 strings.

t2_04edge

Input{"s1":"","s2":""}

Expectedfalse

⏱ Performance - must finish in 2000ms

Empty strings: s1 length zero means no permutation to find; return false.

💡 Check for empty input strings and handle gracefully.

💡 If s1 is empty, no permutation exists; return false.

💡 Add input validation for empty strings at the start.

Why it failed: Returned true or error on empty strings. Fix by returning false if s1 is empty.

✓ Correctly handled empty string inputs.

t3_01corner

Input{"s1":"ab","s2":"eidboaoo"}

Expectedfalse

⏱ Performance - must finish in 2000ms

s2 contains characters from s1 but no substring is a permutation of s1.

💡 Check that all characters in the window match frequency counts exactly, not just presence.

💡 Avoid greedy matching by verifying full frequency equality.

💡 Use a sliding window frequency comparison rather than partial matches.

Why it failed: Returned true incorrectly due to greedy partial matching. Fix by comparing full frequency maps for each window.

✓ Correctly rejected s2 with partial but no full permutation of s1.

t3_02corner

Input{"s1":"aab","s2":"baa"}

Expectedtrue

⏱ Performance - must finish in 2000ms

s2 contains a permutation of s1 with repeated characters, testing correct frequency handling.

💡 Handle repeated characters by counting frequencies, not just unique chars.

💡 Ensure frequency counts match exactly including duplicates.

💡 Sliding window must update counts correctly when characters repeat.

Why it failed: Returned false due to ignoring character counts or treating duplicates as unique. Fix by counting frequencies precisely.

✓ Correctly handled repeated characters in permutations.

t3_03corner

Input{"s1":"abc","s2":"cbaebabacd"}

Expectedtrue

⏱ Performance - must finish in 2000ms

s2 contains multiple permutations of s1; test that function returns true on first found.

💡 Stop searching once a valid permutation is found.

💡 Check all windows of size s1 length for frequency equality.

💡 Use early return to optimize once a match is detected.

Why it failed: Returned false despite multiple permutations present. Fix by checking all windows and returning true on first match.

✓ Correctly detected multiple permutations and returned true.

t4_01performance

Input{"s1":"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","s2":"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}

Expectednull

⏱ Performance - must finish in 2000ms

n=100000, m=100; O(n) sliding window solution must complete within 2 seconds.

💡 Use a sliding window with frequency arrays of fixed size 26.

💡 Avoid recomputing frequency counts from scratch for each window.

💡 Update counts incrementally as the window slides.

Why it failed: TLE due to brute force O(n*m) approach. Fix by implementing O(n) sliding window frequency comparison.

✓ Sliding window solution runs efficiently within time limits.

Practice

1. You are given an array of integers and a fixed window size k. For each contiguous subarray of size k, you need to find the maximum element efficiently. Which of the following approaches guarantees an optimal O(n) time complexity solution?

easy

A. Use a brute force nested loop to check all elements in each window.

B. Use a max-heap (priority queue) to store elements of the current window and extract the max.

C. Use dynamic programming to precompute maximums for overlapping intervals.

D. Maintain a deque that stores indices of elements in decreasing order, removing indices outside the current window.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding maximums for all windows of size k in an array of size n, aiming for an efficient solution.

2. Step 2: Evaluate each approach's time complexity and correctness

   Brute force (nested loops) is O(n*k), max-heap approach is O(n log k), and DP approach is not straightforward here. The deque approach maintains indices in decreasing order and removes outdated indices, achieving O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Deque approach is known as the optimal sliding window maximum solution [OK]

Hint: Monotonic deque achieves O(n) by removing outdated and smaller elements [OK]

Common Mistakes:

• Thinking max-heap is optimal despite log k overhead
• Assuming DP applies directly without preprocessing
• Believing brute force is acceptable for large n

2. Consider the following buggy code for counting binary subarrays with sum equal to goal. Which line contains the subtle bug that causes incorrect counts for subarrays starting at index 0?

def numSubarraysWithSum(nums, goal):
    def atMost(S):
        count = left = 0
        current_sum = 0
        for right, num in enumerate(nums):
            current_sum += num
            while current_sum > S:
                current_sum -= nums[left]
                left += 1
            count += right - left
        return count
    return atMost(goal) - atMost(goal - 1) if goal > 0 else atMost(0)

medium

A. Line 10: The count increment uses 'right - left' instead of 'right - left + 1'.

B. Line 4: Initialization of count and left variables.

C. Line 7: The while loop condition should be 'current_sum >= S' instead of '>'.

D. Line 12: The return statement incorrectly handles the case when goal is zero.

Solution

1. Step 1: Identify count increment logic

   Count should include the current subarray length: number of subarrays ending at right is 'right - left + 1'. Using 'right - left' misses subarrays starting at left.

2. Step 2: Understand impact on subarrays starting at index 0

   Missing '+1' causes undercounting subarrays that start exactly at index 0, leading to incorrect total counts.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct count increment is 'right - left + 1' [OK]

Hint: Count subarrays ending at right as 'right - left + 1' [OK]

Common Mistakes:

• Off-by-one errors in count increments
• Misunderstanding while loop condition
• Incorrect handling of goal=0 case

3. The following code attempts to find all anagrams of p in s using a sliding window with count matching optimization. Which line contains a subtle bug that can cause incorrect results or runtime errors?

medium

A. Line missing decrement of window_count[left_index] when shrinking window

B. Line checking if window_count[index] == p_count[index] + 1 to decrement matches

C. Line incrementing window_count[index] when adding right character

D. Line appending left index to result when matches == 26

Solution

1. Step 1: Identify window shrinking logic

   When window size exceeds p length, left character count must be decremented.

2. Step 2: Locate missing decrement

   The code does not decrement window_count[left_index] before moving left pointer, causing incorrect counts.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing decrement breaks frequency tracking [OK]

Hint: Always decrement count when shrinking window [OK]

Common Mistakes:

• Forgetting to decrement frequency on window shrink
• Incorrect matches update logic
• Appending wrong indices

4. Suppose the problem is modified so that characters can be reused multiple times but you want the longest substring where each character appears at most twice. Which modification to the sliding window approach is correct?

hard

A. Use a hash set to track unique characters and reset the window whenever a duplicate is found

B. Use a dynamic programming approach storing max length substrings ending at each index

C. Use a brute force approach checking all substrings since sliding window cannot handle counts >1

D. Use a hash map to count occurrences of each character and shrink the window when any count exceeds 2

Solution

1. Step 1: Understand the new constraint

   Characters can appear at most twice, so we must track counts, not just presence.

2. Step 2: Modify sliding window

   Use a hash map to count occurrences. Expand right pointer, increment counts. When any count > 2, move left pointer and decrement counts until valid.

3. Step 3: Evaluate other options

   Hash set only tracks presence (not counts), brute force is inefficient, DP is not straightforward here.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Counting occurrences with sliding window handles "at most twice" constraint [OK]

Hint: Track counts, not just presence, for repeated allowed chars [OK]

Common Mistakes:

• Using hash set instead of counts
• Assuming sliding window can't handle counts >1

5. Suppose the problem is modified so that elements in the array can be reused any number of times to form contiguous subarrays (i.e., subarrays can wrap around or repeat elements). Which of the following statements about adapting the sliding window algorithm is correct?

hard

A. The original sliding window algorithm works without changes because product updates remain valid with repeated elements.

B. Using a max-heap to track products allows efficient counting of repeated-element subarrays.

C. The sliding window approach fails because the window can grow indefinitely due to element reuse, requiring a different approach like dynamic programming.

D. We can fix the sliding window by resetting the window whenever product exceeds k, but counting subarrays remains the same.

Solution

1. Step 1: Understand element reuse impact

   Allowing reuse means subarrays can be infinitely long by repeating elements, so the window can grow without bound.

2. Step 2: Sliding window limitation

   Sliding window relies on finite array length and shrinking window when product exceeds k; infinite repetition breaks this logic.

3. Step 3: Alternative approach needed

   Dynamic programming or other methods are needed to handle infinite or repeated elements properly.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Infinite growth breaks sliding window assumptions -> need different approach [OK]

Hint: Infinite repetition breaks sliding window shrinking logic [OK]

Common Mistakes:

• Assuming sliding window works unchanged
• Trying to fix by resets only