Permutation in String

▶

Steps

setup

Initialize variables and frequency count for s1

Calculate lengths of s1 and s2, build frequency count array for s1 characters, and count how many unique characters s1 has.

💡 This setup defines the target frequencies the window must match to find a permutation.

Line:

len_s1, len_s2 = len(s1), len(s2)
count = [0] * 26
for c in s1:
    count[ord(c) - ord('a')] += 1
required = sum(1 for x in count if x > 0)

💡 We now know the target character frequencies and how many unique characters must match.

expand

Expand window: include s2[0] = 'e'

Move right pointer to 0, include 'e' in the window, update window frequency counts. 'e' is not in s1, so formed remains 0.

💡 Expanding the window adds a new character to check if it helps match s1's frequencies.

Line:

idx = ord(s2[right]) - ord('a')
window_count[idx] += 1
if window_count[idx] == count[idx]:
    formed += 1

💡 'e' is not needed, so formed does not increase.

expand

Expand window: include s2[1] = 'i'

Right pointer moves to 1, 'i' added to window. 'i' is not in s1, formed remains 0.

💡 Continue expanding to reach window size equal to s1's length.

Line:

idx = ord(s2[right]) - ord('a')
window_count[idx] += 1
if window_count[idx] == count[idx]:
    formed += 1

💡 'i' does not contribute to matching s1 frequencies.

compare

Window size equals s1 length, check formed

Window size is 2, equal to s1 length. formed is 0, which is less than required 2, so no answer recorded.

💡 We maintain window size equal to s1 length to check fixed-size substrings.

Line:

if right - left + 1 > len_s1:
    ...
if formed == required:
    return True

💡 Window size control is crucial to check valid substrings.

expand

Expand window: include s2[2] = 'd' and shrink from left

Right pointer moves to 2, 'd' added. Window size exceeds s1 length, so remove 'e' from left. 'd' and 'e' are not in s1, formed remains 0.

💡 Sliding window moves forward, maintaining fixed size and updating counts.

Line:

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

💡 Characters outside s1 do not affect formed count but window size is controlled.

expand

Expand window: include s2[3] = 'b' and shrink from left

Right pointer moves to 3, 'b' added. Window size exceeds s1 length, so remove 'i' from left. 'b' is in s1 and window_count['b'] matches count['b'], so formed increases to 1.

💡 Including a needed character can increase the formed count, bringing us closer to a match.

Line:

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

💡 Matching frequency for 'b' increases formed count.

expand

Expand window: include s2[4] = 'a' and shrink from left

Right pointer moves to 4, 'a' added. Window size exceeds s1 length, so remove 'd' from left. 'a' is in s1 and window_count['a'] matches count['a'], so formed increases to 2.

💡 Now formed equals required, meaning the window contains a permutation of s1.

Line:

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

💡 Window now matches all required character frequencies.

compare

Check if formed equals required and return true

Since formed equals required, the algorithm returns true indicating s2 contains a permutation of s1.

💡 Detecting formed == required means the current window is a valid permutation.

Line:

if formed == required:
    return True

💡 The algorithm successfully found a permutation without checking all substrings.

expand

Expand window: include s2[5] = 'o' and shrink from left

Right pointer moves to 5, 'o' added. Window size exceeds s1 length, so remove 'b' from left. 'o' is not in s1, formed decreases from 2 to 1 because 'b' was matched and is removed.

💡 Continuing the sliding window movement after finding a match shows how formed updates when matched characters leave the window.

Line:

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

💡 Removing a matched character from the window decreases formed, showing how the algorithm tracks valid windows dynamically.

reconstruct

Final state: answer is true

The algorithm terminates with answer true, indicating s2 contains a permutation of s1 in the window from index 3 to 4.

💡 The final state confirms the substring that is a permutation.

Line:

return True

💡 The sliding window approach efficiently finds the answer without brute force.

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

📊

Permutation in String - Watch the Algorithm Execute, Step by Step

Watching each step of the sliding window and frequency matching reveals how the algorithm efficiently checks for permutations without generating all permutations explicitly.

setup

L ▼

e

0

i

1

d

2

b

3

a

4

o

5

o

6

o

7

Metric:

count_s1:

a: 1

b: 1

required: 2

formed: 0

window_count:

Answer:

expand

L=R

e

0

i

1

d

2

b

3

a

4

o

5

o

6

o

7

Window: [e]

Metric:

count_s1:

a: 1

b: 1

required: 2

formed: 0

window_count:

e: 1

Answer:

expand

L ▼

e

0

R ▼

i

1

d

2

b

3

a

4

o

5

o

6

o

7

Window: [e, i]

Metric:

count_s1:

a: 1

b: 1

required: 2

formed: 0

window_count:

e: 1

i: 1

Answer:

record_answer

L ▼

e

0

R ▼

i

1

d

2

b

3

a

4

o

5

o

6

o

7

Window: [e, i]

Metric:

count_s1:

a: 1

b: 1

required: 2

formed: 0

window_count:

e: 1

i: 1

Answer:

expand

e

0

L ▼

i

1

R ▼

d

2

b

3

a

4

o

5

o

6

o

7

Window: [i, d]

Metric:

count_s1:

a: 1

b: 1

required: 2

formed: 0

window_count:

i: 1

d: 1

Answer:

expand

e

0

i

1

L ▼

d

2

R ▼

b

3

a

4

o

5

o

6

o

7

Window: [d, b]

Metric:

count_s1:

a: 1

b: 1

required: 2

formed: 1

window_count:

d: 1

b: 1

Answer:

expand

e

0

i

1

d

2

L ▼

b

3

R ▼

a

4

o

5

o

6

o

7

Window: [b, a]

Metric:

count_s1:

a: 1

b: 1

required: 2

formed: 2

window_count:

b: 1

a: 1

Answer:

record_answer

e

0

i

1

d

2

L ▼

b

3

R ▼

a

4

o

5

o

6

o

7

Window: [b, a]

Metric:

count_s1:

a: 1

b: 1

required: 2

formed: 2

window_count:

b: 1

a: 1

Answer:

expand

e

0

i

1

d

2

b

3

L ▼

a

4

R ▼

o

5

o

6

o

7

Window: [a, o]

Metric:

count_s1:

a: 1

b: 1

required: 2

formed: 1

window_count:

a: 1

o: 1

Answer:

record_answer

e

0

i

1

d

2

L ▼

b

3

R ▼

a

4

o

5

o

6

o

7

Window: [b, a]

Metric:

count_s1:

a: 1

b: 1

required: 2

formed: 2

window_count:

b: 1

a: 1

Answer:

Key Takeaways

✓ Tracking the number of characters with matching frequencies (formed) is more efficient than checking entire frequency arrays each time.

This insight is hard to see from code alone because it requires understanding why formed updates correctly reflect window validity.

✓ The sliding window maintains a fixed size equal to s1's length, ensuring only relevant substrings are checked.

Visualizing the window size control clarifies why the algorithm doesn't waste time on invalid substrings.

✓ When a character frequency matches exactly, formed increments; when it falls out of sync, formed decrements, enabling quick detection of valid windows.

Seeing formed change step-by-step helps understand the match count optimization's correctness.

Practice

1. Given the following code and input cardPoints = [4, 2, 3, 1], k = 2, what is the value of min_subarray_sum after the loop finishes?

easy

A. 3

B. 5

C. 4

D. 6

Solution

1. Step 1: Calculate initial sums

   n=4, k=2, window_size=2, current_sum=sum([4,2])=6, min_subarray_sum=6

2. Step 2: Iterate over the array

   i=2: current_sum=6 + 3 - 4 = 5, min_subarray_sum=5
   i=3: current_sum=5 + 1 - 2 = 4, min_subarray_sum=4

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Minimum subarray sum found is 4 after sliding window moves [OK]

Hint: Sliding window updates sum by adding new and removing old element [OK]

Common Mistakes:

• Off-by-one error in loop range
• Incorrect initial window sum
• Not updating min_subarray_sum correctly

2. Consider the following Python function implementing the sliding window approach to find the maximum sum subarray of size k. What is the value of window_sum after the second iteration of the for-loop when called with arr = [1, 3, 2, 6] and k = 2?

def max_sum_subarray_sliding_window(arr, k):
    n = len(arr)
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, n):
        window_sum += arr[i] - arr[i - k]
        if window_sum > max_sum:
            max_sum = window_sum
    return max_sum

easy

A. 8

B. 9

C. 5

D. 7

Solution

1. Step 1: Initialize variables

   window_sum = sum(arr[:2]) = 1 + 3 = 4, max_sum = 4

2. Step 2: Iterate and update window_sum

   First iteration (i=2): window_sum = 4 + arr[2] - arr[0] = 4 + 2 - 1 = 5 Second iteration (i=3): window_sum = 5 + arr[3] - arr[1] = 5 + 6 - 3 = 8

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   window_sum after second iteration is 8 [OK]

Hint: Track window_sum updates carefully per iteration [OK]

Common Mistakes:

• Off-by-one errors in loop index
• Confusing window_sum with max_sum
• Forgetting to subtract the element leaving the window

3. You are given an array of integers representing cards laid out in a row. You want to find the length of the shortest contiguous subarray that contains at least one duplicate card. Which algorithmic approach guarantees the optimal solution with linear time complexity?

easy

A. Brute force nested loops checking all subarrays for duplicates

B. Sliding window combined with a map tracking last seen indices of cards

C. Dynamic programming to store minimum subarray lengths ending at each index

D. Greedy approach picking cards from left until a duplicate is found

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the shortest subarray containing duplicates, which suggests tracking duplicates efficiently.

2. Step 2: Evaluate approaches

   Brute force (A) is correct but inefficient (O(n²)). DP (C) is not suitable since no overlapping subproblems are exploited. Greedy (D) fails because it doesn't guarantee minimal length. Sliding window with last seen map (B) achieves O(n) by moving pointers smartly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sliding window with last seen map is the known optimal approach [OK]

Hint: Sliding window + last seen map -> O(n) optimal

Common Mistakes:

• Thinking greedy approach always finds minimal subarray
• Assuming DP applies without overlapping subproblems

4. The following code attempts to find the maximum sum subarray of size k using the sliding window approach. Identify the line that contains a subtle bug that may cause incorrect results when the array contains all negative numbers.

def max_sum_subarray_sliding_window(arr, k):
    n = len(arr)
    window_sum = sum(arr[:k])
    max_sum = 0
    for i in range(k, n):
        window_sum += arr[i] - arr[i - k]
        if window_sum > max_sum:
            max_sum = window_sum
    return max_sum

medium

A. Line 4: Initializing max_sum to 0 instead of a smaller value.

B. Line 5: Loop starting from index k instead of k-1.

C. Line 3: Initializing window_sum with sum of first k elements.

D. Line 6: Updating window_sum by adding arr[i] and subtracting arr[i - k].

Solution

1. Step 1: Understand initialization of max_sum

   max_sum is initialized to 0, which is incorrect if all array elements are negative because the maximum sum could be less than 0.

2. Step 2: Consequence of wrong initialization

   If all sums are negative, max_sum remains 0, which is incorrect. Proper initialization should be max_sum = window_sum (sum of first k elements) or float('-inf').

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   max_sum initialized to 0 causes incorrect max for negative arrays [OK]

Hint: Initialize max_sum to first window sum, not zero [OK]

Common Mistakes:

• Initializing max_sum to zero instead of first window sum
• Off-by-one errors in loop indices
• Incorrect window_sum updates

5. What is the time complexity of the sliding window approach for the Minimum Size Subarray Sum problem, and why might some candidates incorrectly think it is O(n²)?

medium

A. O(n log n) due to sorting or binary search inside the loop

B. O(n²) because of nested loops implied by two pointers

C. O(n) because each element is visited at most twice by left and right pointers

D. O(n) but with O(n) auxiliary space for prefix sums

Solution

1. Step 1: Identify pointer movements

   Right pointer moves forward once per iteration; left pointer moves forward only when shrinking window, each element visited at most twice.

2. Step 2: Analyze total operations

   Since both pointers only move forward, total operations are proportional to 2n = O(n), no nested repeated scanning.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two-pointer sliding window is classic O(n) approach [OK]

Hint: Two pointers each move forward once -> O(n) [OK]

Common Mistakes:

• Assuming nested loops cause O(n²)
• Confusing prefix sums with sliding window
• Thinking auxiliary space affects time complexity