Code Templates

String manipulation requires a mix of pointer logic and frequency tracking. Below are the most common templates used to solve

O(N)

string problems.

For the theoretical background, check out the Concept Guide.

The Main Template: Sliding Window with Frequency Map

This template is the gold standard for problems like “Minimum Window Substring” or “Find All Anagrams.” It uses a frequency map to track character requirements.

/**
 * Generic Sliding Window for String Problems
 * @param {string} s - Search string
 * @param {string} t - Pattern/Target string
 */
function slidingWindow(s, t) {
    const need = new Map();
    const window = new Map();
    for (const char of t) need.set(char, (need.get(char) || 0) + 1);

    let left = 0, right = 0;
    let valid = 0;

    // Result tracking variables (adjust based on problem)
    let start = 0, len = Infinity;

    while (right < s.length) {
        const char = s[right];
        right++;

        // Window Update: Add character from right
        if (need.has(char)) {
            window.set(char, (window.get(char) || 0) + 1);
            if (window.get(char) === need.get(char)) valid++;
        }

        // Window Contraction: Shrink from left
        while (valid === need.size) {
            // Update results here (e.g., min length)
            if (right - left < len) {
                start = left;
                len = right - left;
            }

            const d = s[left];
            left++;

            // Window Update: Remove character from left
            if (need.has(d)) {
                if (window.get(d) === need.get(d)) valid--;
                window.set(d, window.get(d) - 1);
            }
        }
    }
    return len === Infinity ? "" : s.substr(start, len);
}

def sliding_window(s: str, t: str) -> str:
    from collections import Counter

    need = Counter(t)
    window = Counter()

    left = right = 0
    valid = 0

    # Result tracking
    start, length = 0, float('inf')

    while right < len(s):
        char = s[right]
        right += 1

        if char in need:
            window[char] += 1
            if window[char] == need[char]:
                valid += 1

        # Shrink condition
        while valid == len(need):
            if right - left < length:
                start = left
                length = right - left

            d = s[left]
            left += 1

            if d in need:
                if window[d] == need[d]:
                    valid -= 1
                window[d] -= 1

    return "" if length == float('inf') else s[start:start + length]

import java.util.*;

public class Solution {
    public String slidingWindow(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        for (char c : t.toCharArray()) need.put(c, need.getOrDefault(c, 0) + 1);

        int left = 0, right = 0;
        int valid = 0;
        int start = 0, len = Integer.MAX_VALUE;

        while (right < s.length()) {
            char c = s.charAt(right);
            right++;

            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) valid++;
            }

            while (valid == need.size()) {
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }

                char d = s.charAt(left);
                left++;

                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) valid--;
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}

#include <string>
#include <unordered_map>
#include <climits>

using namespace std;

string slidingWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0;
    int start = 0, len = INT_MAX;

    while (right < s.size()) {
        char c = s[right];
        right++;

        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c]) valid++;
        }

        while (valid == need.size()) {
            if (right - left < len) {
                start = left;
                len = right - left;
            }

            char d = s[left];
            left++;

            if (need.count(d)) {
                if (window[d] == need[d]) valid--;
                window[d]--;
            }
        }
    }
    return len == INT_MAX ? "" : s.substr(start, len);
}

func slidingWindow(s string, t string) string {
    need := make(map[byte]int)
    window := make(map[byte]int)
    for i := 0; i < len(t); i++ {
        need[t[i]]++
    }

    left, right := 0, 0
    valid := 0
    start, length := 0, 1<<31 - 1

    for right < len(s) {
        c := s[right]
        right++

        if _, ok := need[c]; ok {
            window[c]++
            if window[c] == need[c] {
                valid++
            }
        }

        for valid == len(need) {
            if right-left < length {
                start = left
                length = right - left
            }

            d := s[left]
            left++

            if _, ok := need[d]; ok {
                if window[d] == need[d] {
                    valid--
                }
                window[d]--
            }
        }
    }

    if length == 1<<31 - 1 {
        return ""
    }
    return s[start : start+length]
}

def sliding_window(s, t)
  need = Hash.new(0)
  t.each_char { |c| need[c] += 1 }

  window = Hash.new(0)
  left = right = 0
  valid = 0

  start = 0
  len = Float::INFINITY

  while right < s.length
    char = s[right]
    right += 1

    if need.key?(char)
      window[char] += 1
      valid += 1 if window[char] == need[char]
    end

    while valid == need.size
      if right - left < len
        start = left
        len = right - left
      end

      d = s[left]
      left += 1

      if need.key?(d)
        valid -= 1 if window[d] == need[d]
        window[d] -= 1
      end
    end
  end

  len == Float::INFINITY ? "" : s[start, len]
end

Code Breakdown

1. Variables

need: Hash map storing characters we need and their required frequencies.
window: Hash map tracking characters currently inside our window.
left / right: The boundaries of our sliding window.
valid: The count of characters that meet the frequency requirement.

2. The Logic Flow

  graph TD
    Start([Start]) --> Expand[1. Move 'right' to expand window]
    Expand --> Check{Is character in 'need'?}
    Check -- Yes --> UpdateWin[Update 'window' & 'valid' count]
    Check -- No --> ShrinkCheck
    UpdateWin --> ShrinkCheck
    ShrinkCheck{Is 'valid' == 'need.size'?}
    ShrinkCheck -- Yes --> UpdateResult[2. Update best result & Move 'left' to shrink]
    UpdateResult --> ShrinkCheck
    ShrinkCheck -- No --> EndCheck{Is 'right' at end?}
    EndCheck -- No --> Expand
    EndCheck -- Yes --> End([End])

Expansion: We keep moving the right pointer to include more characters until the window satisfies all conditions in need.
Contraction: Once the condition is met, we try to shrink the window from the left as much as possible to find the minimal valid window.

Variation: Two Pointers (In-place Swap)

Used for reversing strings or moving elements without extra space.

function reverseString(s) {
    let left = 0, right = s.length - 1;
    while (left < right) {
        [s[left], s[right]] = [s[right], s[left]];
        left++;
        right--;
    }
}

def reverse_string(s: list[str]) -> None:
    left, right = 0, len(s) - 1
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1

public void reverseString(char[] s) {
    int left = 0, right = s.length - 1;
    while (left < right) {
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        left++;
        right--;
    }
}

void reverseString(vector<char>& s) {
    int left = 0, right = s.size() - 1;
    while (left < right) {
        swap(s[left++], s[right--]);
    }
}

func reverseString(s []byte) {
    left, right := 0, len(s)-1
    for left < right {
        s[left], s[right] = s[right], s[left]
        left++
        right--
    }
}

def reverse_string(s)
  left = 0
  right = s.length - 1
  while left < right
    s[left], s[right] = s[right], s[left]
    left += 1
    right -= 1
  end
end

Practice

Test these templates on real problems in the Practice Problems section.