Lab: string problems
Three guided exercises combining sliding window, two-pointer, and hashing — character replacement, palindrome check, and anagram search.
- Solve character replacement using a variable sliding window
- Solve palindrome check with two-pointer on cleaned input
- Find all anagram positions using a sliding frequency window
Three problems that draw on each technique from this module. Each has a "think first" prompt — resist scrolling to the starter code until you have a rough plan.
Problem 1: character replacement
Problem. Given a string s and an integer k, return the length of the
longest substring you can make so that all characters are the same, after
replacing at most k characters.
character_replacement("AABABBA", 1) → 4.
Think first. Use a variable sliding window. Track the frequency of each
character in the window. The window is valid when
(window size) - (count of most frequent char) <= k. If the window becomes
invalid, slide the left pointer one step right (keeping the window size
stable — this is a standard trick: never shrink the window below the current
best, only grow it).
Implement character_replacement(s, k) returning the longest substring length where at most k replacements make all chars identical. Use a variable sliding window.
character_replacement("AABABBA", 1) → 4character_replacement("ABAB", 2) → 4Problem 2: palindrome check (raw input)
Problem. Given a string that may contain spaces and punctuation, return
True if it is a palindrome when you ignore non-alphanumeric characters and
treat letters as case-insensitive.
is_palindrome_two_ptr("A man, a plan, a canal: Panama") → True.
Think first. Two-pointer from both ends. Skip non-alphanumeric characters as you move each pointer inward. Compare lowercased alphanumeric characters only. This avoids building a new string — O(1) extra space.
Implement is_palindrome_two_ptr(s). Skip non-alphanumeric chars and compare case-insensitively. O(n) time, O(1) extra space.
is_palindrome_two_ptr("A man, a plan, a canal: Panama") → Trueis_palindrome_two_ptr("race a car") → FalseProblem 3: find all anagram positions
Problem. Given strings s and p, return the start indices of all
substrings of s that are anagrams of p.
find_all_anagrams("cbaebabacd", "abc") → [0, 6].
Think first. Use a fixed-size sliding window of length len(p). Maintain
a frequency counter for the current window in s and compare it to the
frequency counter for p. Updating the window is O(1) per step: add the
incoming character, remove the outgoing one.
Implement find_all_anagrams(s, p) returning a list of start indices where a p-length anagram of p appears in s. Use a fixed sliding window of size len(p).
find_all_anagrams("cbaebabacd", "abc") → [0, 6]find_all_anagrams("abab", "ab") → [0, 1, 2]Comparing two Counter objects with == is O(k) where k is the number of
distinct characters — at most 26 for lowercase English. For the purposes of
this problem that is effectively O(1), making the overall algorithm O(n).
Where to go next
Next: the Algorithm Design Paradigms module — greedy algorithms, divide and conquer, and backtracking, and how to recognise which paradigm applies to a new problem.