Tag substring problems

Sliding Window Technique Interview Questions in C: A Comprehensive Tutorial

The Sliding Window Technique is a top-tier interview topic because it appears in dozens of variations across array, string, and streaming problems. Interviewers test both your conceptual understanding and your ability to implement it correctly in C with safe memory practices.

This tutorial combines 20 curated interview questions with model answers and full C implementations of the most representative problems across easy, medium, and hard levels. Each code block is C99/C11-compliant, includes explicit memory management, and has verified expected output.

---

Conceptual Introduction & Fundamentals

What is the Sliding Window Technique?

The Sliding Window Technique processes a contiguous range of elements (a “window”) by expanding or shrinking it as it traverses the data, reusing work from the previous window instead of recomputing.

Core properties:

• Maintains a window using two pointers (usually left and right).
• Each element enters and leaves the window at most once → O(n) time.
• Uses O(1) to O(k) auxiliary space depending on the problem.
• Works on arrays, strings, and streams.

Why Interviewers Love It

• Discriminating: Separates candidates who can reason about invariants.
• Practical: Appears in real systems (network buffers, log analysis).
• Composable: Combines with hashing, deques, and prefix sums.
• Testable: Easy to design follow-up questions.

The Two Variants

Variant	Window Size	Typical Problems
Fixed-Size	Constant k given	Max sum of size k, averages, anagram counts
Variable-Size	Depends on condition	Longest unique substring, minimum window

When Not to Use Sliding Window

• Non-contiguous subsets (use DP or brute force).
• Arbitrary reordering (use sorting or hashing).
• Conditions that are not monotone over the window.

---

Syntax & Core Mechanics

Fixed-Size Template

c

/* Compute initial window sum for [0, k-1] */ long long window = 0; for (int i = 0; i < k; i++) window += arr[i]; long long best = window; /* Slide: subtract outgoing, add incoming */ for (int i = k; i < n; i++) { window += arr[i] - arr[i - k]; if (window > best) best = window; }

Variable-Size Template

c

int left = 0; /* Optional: state (freq map, sum, count) */ for (int right = 0; right < n; right++) { /* 1. Include arr[right] into state */ /* 2. While invariant violated, shrink from left */ while (/* invariant violated */) { /* remove arr[left] from state */ left++; } /* 3. Update best answer using [left, right] */ }

Key Invariant

For variable-size windows, we maintain:

All elements in [left, right] satisfy the problem’s condition, and right - left + 1 is the current candidate.

When the condition breaks, shrink left until the condition holds again.

---

Full Practical Code Example with Explanation

Below are six complete C programs covering the most-asked interview problems. Each is self-contained, C99/C11-compliant, and includes expected output.

Problem 1: Maximum Sum of Subarray of Size k (Easy)

c

#include <stdio.h> #include <limits.h> long long maxSumFixedK(const int arr[], int n, int k) { if (k <= 0 || n < k) return LLONG_MIN; long long window = 0; for (int i = 0; i < k; i++) window += arr[i]; long long best = window; for (int i = k; i < n; i++) { window += arr[i] - arr[i - k]; if (window > best) best = window; } return best; } int main(void) { int arr[] = {5, 2, -1, 0, 3}; int n = sizeof(arr) / sizeof(arr[0]); printf("%lld\n", maxSumFixedK(arr, n, 3)); /* 6 */ return 0; }

Expected output:

text

6

Time: O(n), Space: O(1)

Problem 2: Longest Substring Without Repeating Characters (Medium)

c

#include <stdio.h> int longestUnique(const char *s) { int lastSeen[256]; for (int i = 0; i < 256; i++) lastSeen[i] = -1; int left = 0, best = 0; for (int right = 0; s[right] != '\0'; right++) { unsigned char c = (unsigned char)s[right]; if (lastSeen[c] >= left) left = lastSeen[c] + 1; lastSeen[c] = right; int len = right - left + 1; if (len > best) best = len; } return best; } int main(void) { printf("%d\n", longestUnique("abcabcbb")); /* 3 */ printf("%d\n", longestUnique("bbbbb")); /* 1 */ printf("%d\n", longestUnique("pwwkew")); /* 3 */ return 0; }

Expected output:

text

3 1 3

Time: O(n), Space: O(1)

Problem 3: Longest Repeating Character Replacement (Medium)

Given a string and integer k, find the longest substring that can be turned into a single repeated character using at most k replacements.

c

#include <stdio.h> int characterReplacement(const char *s, int k) { int count[26] = {0}; int left = 0, maxCount = 0, best = 0; for (int right = 0; s[right] != '\0'; right++) { int idx = s[right] - 'A'; count[idx]++; if (count[idx] > maxCount) maxCount = count[idx]; /* window size = right - left + 1; replacements needed = window size - maxCount */ while ((right - left + 1) - maxCount > k) { count[s[left] - 'A']--; left++; } int len = right - left + 1; if (len > best) best = len; } return best; } int main(void) { printf("%d\n", characterReplacement("AABABBA", 1)); /* 4 */ printf("%d\n", characterReplacement("ABAB", 2)); /* 4 */ return 0; }

Expected output:

text

4 4

Time: O(n), Space: O(1)

Problem 4: Minimum Window Substring (Hard)

Find the smallest substring of s that contains all characters of t (with multiplicities).

c

#include <stdio.h> #include <string.h> #include <limits.h> void minWindow(const char *s, const char *t, char *result, int resultSize) { result[0] = '\0'; if (t[0] == '\0' || s[0] == '\0') return; int need[256] = {0}, have[256] = {0}; int required = 0; for (int i = 0; t[i] != '\0'; i++) { if (need[(unsigned char)t[i]] == 0) required++; need[(unsigned char)t[i]]++; } int left = 0, formed = 0; int bestLen = INT_MAX, bestL = -1; int sLen = (int)strlen(s); for (int right = 0; right < sLen; right++) { unsigned char c = (unsigned char)s[right]; have[c]++; if (need[c] > 0 && have[c] == need[c]) formed++; while (formed == required) { int len = right - left + 1; if (len < bestLen) { bestLen = len; bestL = left; } unsigned char lc = (unsigned char)s[left]; have[lc]--; if (need[lc] > 0 && have[lc] < need[lc]) formed--; left++; } } if (bestL != -1 && bestLen < resultSize) { memcpy(result, s + bestL, (size_t)bestLen); result[bestLen] = '\0'; } } int main(void) { char result[256]; minWindow("ADOBECODEBANC", "ABC", result, sizeof(result)); printf("%s\n", result); /* BANC */ minWindow("a", "a", result, sizeof(result)); printf("%s\n", result); /* a */ minWindow("a", "aa", result, sizeof(result)); printf("\"%s\"\n", result); /* "" */ return 0; }

Expected output:

text

BANC a ""

Time: O(|s| + |t|), Space: O(1)

Problem 5: Maximum Consecutive 1s with K Flips (Medium)

Given a binary array and k flips allowed, find the longest subarray of all 1s.

c

#include <stdio.h> int longestOnes(const int arr[], int n, int k) { int left = 0, zeros = 0, best = 0; for (int right = 0; right < n; right++) { if (arr[right] == 0) zeros++; while (zeros > k) { if (arr[left] == 0) zeros--; left++; } int len = right - left + 1; if (len > best) best = len; } return best; } int main(void) { int arr1[] = {1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0}; int arr2[] = {0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1}; printf("%d\n", longestOnes(arr1, 11, 2)); /* 6 */ printf("%d\n", longestOnes(arr2, 19, 3)); /* 10 */ return 0; }

Expected output:

text

6 10

Time: O(n), Space: O(1)

Problem 6: Count Distinct Elements in Every Window of Size K (Medium)

For each window of size k, count distinct elements.

c

#include <stdio.h> #include <stdlib.h> #define TABLE_SIZE 4096 typedef struct { int *keys; int *counts; int *occupied; int capacity; } FreqMap; static unsigned int hashFunc(int key, int cap) { return ((unsigned int)key) % (unsigned int)cap; } static FreqMap *mapCreate(int cap) { FreqMap *m = malloc(sizeof(FreqMap)); if (m == NULL) return NULL; m->keys = malloc((size_t)cap * sizeof(int)); m->counts = calloc((size_t)cap, sizeof(int)); m->occupied = calloc((size_t)cap, sizeof(int)); if (m->keys == NULL || m->counts == NULL || m->occupied == NULL) { free(m->keys); free(m->counts); free(m->occupied); free(m); return NULL; } m->capacity = cap; return m; } static void mapFree(FreqMap *m) { if (m) { free(m->keys); free(m->counts); free(m->occupied); free(m); } } static int mapAdd(FreqMap *m, int key) { unsigned int idx = hashFunc(key, m->capacity); int start = (int)idx; while (m->occupied[idx]) { if (m->keys[idx] == key) { m->counts[idx]++; return m->counts[idx]; } idx = (idx + 1) % (unsigned int)m->capacity; if ((int)idx == start) return -1; } m->keys[idx] = key; m->counts[idx] = 1; m->occupied[idx] = 1; return 1; } static void mapRemove(FreqMap *m, int key) { unsigned int idx = hashFunc(key, m->capacity); int start = (int)idx; while (m->occupied[idx]) { if (m->keys[idx] == key) { m->counts[idx]--; return; } idx = (idx + 1) % (unsigned int)m->capacity; if ((int)idx == start) return; } } static int mapDistinct(FreqMap *m) { int d = 0; for (int i = 0; i < m->capacity; i++) if (m->occupied[i] && m->counts[i] > 0) d++; return d; } void countDistinctInWindows(const int arr[], int n, int k) { FreqMap *m = mapCreate(TABLE_SIZE); if (m == NULL) return; for (int i = 0; i < k; i++) mapAdd(m, arr[i]); printf("%d ", mapDistinct(m)); for (int i = k; i < n; i++) { mapRemove(m, arr[i - k]); mapAdd(m, arr[i]); printf("%d ", mapDistinct(m)); } printf("\n"); mapFree(m); } int main(void) { int arr[] = {1, 2, 1, 3, 4, 2, 3}; int n = 7, k = 4; countDistinctInWindows(arr, n, k); /* 3 4 4 3 */ return 0; }

Expected output:

text

3 4 4 3

Time: O(n) average, Space: O(k)

---

Common Pitfalls, Edge Cases & Memory Considerations

1. Off-by-One in Window Size

The window [left, right] has size right - left + 1. Double-check inclusive bounds.

2. Non-Monotone Invariant

Sliding windows require the condition to monotonically improve as you shrink. Sum-with-negatives problems often violate this — use prefix sums instead.

3. Duplicate Handling in Frequency Maps

When shrinking, decrement counts; do not remove entries entirely (else your map’s occupied markers corrupt probes).

4. Initialization of the First Window

For fixed-size windows, initialize before entering the slide loop. Off-by-one here is the most common bug.

5. Integer Overflow

Use long long for sums and products.

6. Character Arrays and unsigned char

Negative char values (e.g., extended ASCII) index arrays with wraparound. Cast to unsigned char.

7. Empty Inputs

Always guard n <= 0 or s[0] == '\0'.

8. k > n or k = 0

Define and enforce semantics.

9. Variable Window When left > right

Some problems require resetting left = right when shrunk past the right boundary.

10. Memory Considerations

• Fixed-size windows: O(1) space.
• Variable-size with frequency map: O(k) or O(alphabet).
• For substring problems, size frequency arrays to 256 (or larger for Unicode).
• Free all dynamically allocated memory.

---

Summary & Best Practices

The Sliding Window Technique is a cornerstone of array and string interview problems. Mastering its two variants—fixed-size and variable-size—unlocks an entire family of linear-time solutions.

Key Takeaways

• Two variants: fixed-size (constant k) and variable-size (condition-driven).
• Each element enters and leaves the window at most once → O(n).
• Invariant must be monotone: shrinking must restore validity.
• Hash maps and frequency arrays integrate cleanly with the window.
• Not every subarray problem is a sliding window problem.

Best Practices

1. Identify the window type before writing code.
2. Initialize the first window explicitly for fixed-size problems.
3. Use long long for sums and large counters.
4. Cast char to unsigned char before indexing arrays.
5. Keep the invariant simple — one line that captures the goal.
6. Prefer frequency arrays over hash maps for small alphabets.
7. Free dynamic memory on all exit paths.
8. Test with edge cases: empty, single element, k = 0, k = n, k > n.
9. Verify with a brute-force solution for small inputs.
10. Master the pattern, not just the specific problem — the interview will vary.

Recommended Practice List (from the source)

• Easy: Maximum sum subarray of size k; Smallest window containing 0, 1, 2; Permutation substring; Strictly increasing subarrays; Remove consecutive characters.
• Medium: Longest substring with distinct characters; Substrings with K Distinct; Maximum Consecutive 1s with K Flips; Maximum Fruits in Two Baskets; Minimum Window; Binary Subarray with Sum; Longest Repeating Character Replacement; Count Anagrams.
• Hard: Maximum of Minimum for Every Window Size; Longest Substring with K Uniques; Minimum Window Substring; Largest Sum Subarray with At Least k Numbers.

Working through these problems with the templates above will solidify the pattern.