Implementing a Sliding Window Algorithm Template in C
Tech
2
Sliding window algorithms efficiently solve substring and subarray problems with linear time complexity. This technique uses two pointers to define a window that expands and contracts based on conditions.
A basic sliding window structure in C:
#include <stdio.h>
#include <string.h>
void slidingWindow(char* input) {
int start = 0, end = 0;
int length = strlen(input);
while (end < length) {
// Expand window
char current = input[end];
end++;
// Process window data
// Shrink window when needed
while (/* condition to shrink */) {
char removed = input[start];
start++;
// Update window data
}
}
}
This approach maintains O(N) time complexity since each element enters and exits the window at most once.
A more complete template with helper functions:
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define CHAR_SET 128 // For ASCII characters
typedef struct {
int counts[CHAR_SET];
} CharCounter;
void addChar(CharCounter* counter, char ch) {
counter->counts[(int)ch]++;
}
void removeChar(CharCounter* counter, char ch) {
counter->counts[(int)ch]--;
}
bool needsShrink(CharCounter* window, CharCounter* target) {
// Implementation depends on specific problem
return false;
}
void slidingWindowTemplate(char* str) {
CharCounter window = {0};
CharCounter target = {0};
int left = 0, right = 0;
int strLen = strlen(str);
while (right < strLen) {
// Add character to window
char incoming = str[right];
addChar(&window, incoming);
right++;
// Shrink window when condition met
while (left < right && needsShrink(&window, &target)) {
char outgoing = str[left];
removeChar(&window, outgoing);
left++;
}
}
}
Minimum Window Substring
Find the smallest substring containing all characters of a target string:
#include <stdio.h>
#include <string.h>
#include <limits.h>
char* findMinWindow(char* source, char* target) {
int need[128] = {0};
int window[128] = {0};
int targetLen = strlen(target);
for (int i = 0; i < targetLen; i++) {
need[target[i]]++;
}
int left = 0, right = 0;
int matched = 0;
int minStart = 0, minLength = INT_MAX;
int sourceLen = strlen(source);
while (right < sourceLen) {
char ch = source[right];
right++;
if (need[ch] > 0) {
window[ch]++;
if (window[ch] == need[ch]) {
matched++;
}
}
while (matched == targetLen) {
if (right - left < minLength) {
minStart = left;
minLength = right - left;
}
char removed = source[left];
left++;
if (need[removed] > 0) {
if (window[removed] == need[removed]) {
matched--;
}
window[removed]--;
}
}
}
if (minLength == INT_MAX) {
char* empty = (char*)malloc(1);
empty[0] = '\0';
return empty;
}
char* result = (char*)malloc(minLength + 1);
strncpy(result, source + minStart, minLength);
result[minLength] = '\0';
return result;
}
String Permutation Check
Determine if one string contains a permutation of another:
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool hasPermutation(char* pattern, char* text) {
int patternCount[26] = {0};
int windowCount[26] = {0};
int patternLen = strlen(pattern);
int textLen = strlen(text);
for (int i = 0; i < patternLen; i++) {
patternCount[pattern[i] - 'a']++;
}
int left = 0, right = 0;
int validChars = 0;
while (right < textLen) {
char current = text[right] - 'a';
right++;
if (patternCount[current] > 0) {
windowCount[current]++;
if (windowCount[current] <= patternCount[current]) {
validChars++;
}
}
while (right - left >= patternLen) {
if (validChars == patternLen) {
return true;
}
char removed = text[left] - 'a';
left++;
if (patternCount[removed] > 0) {
if (windowCount[removed] <= patternCount[removed]) {
validChars--;
}
windowCount[removed]--;
}
}
}
return false;
}
Find All Anagrams
Locate all starting indices of anagrams in a string:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int* findAllAnagrams(char* text, char* pattern, int* resultCount) {
int patternLen = strlen(pattern);
int textLen = strlen(text);
int patternFreq[26] = {0};
int windowFreq[26] = {0};
for (int i = 0; i < patternLen; i++) {
patternFreq[pattern[i] - 'a']++;
}
int* indices = (int*)malloc(textLen * sizeof(int));
*resultCount = 0;
int left = 0, right = 0;
int matches = 0;
while (right < textLen) {
char ch = text[right] - 'a';
right++;
if (patternFreq[ch] > 0) {
windowFreq[ch]++;
if (windowFreq[ch] <= patternFreq[ch]) {
matches++;
}
}
while (right - left >= patternLen) {
if (matches == patternLen) {
indices[*resultCount] = left;
(*resultCount)++;
}
char removed = text[left] - 'a';
left++;
if (patternFreq[removed] > 0) {
if (windowFreq[removed] <= patternFreq[removed]) {
matches--;
}
windowFreq[removed]--;
}
}
}
return indices;
}
Longest Substring Without Repeating Charactres
Find the length of the longest substring with distinct characters:
#include <stdio.h>
#include <string.h>
int longestUniqueSubstring(char* str) {
int length = strlen(str);
int charSet[128] = {0};
int start = 0, end = 0;
int maxLength = 0;
while (end < length) {
char current = str[end];
end++;
charSet[current]++;
while (charSet[current] > 1) {
char removed = str[start];
start++;
charSet[removed]--;
}
if (end - start > maxLength) {
maxLength = end - start;
}
}
return maxLength;
}
Key considerations when implementing sliding window algorithms:
- Determine when to expand the window
- Identify conditions for shrinking the window
- Decide when to update results
- Choose appropriate data structures for tracking window contents
