5 patterns · 25 problems
Strings
Two pointers, sliding windows, hashmaps, and pattern matching applied to characters and substrings.
Each pattern below starts with when to reach for it and the clue in the prompt that gives it away. Then it runs on real problems: pick one to watch the technique step by step, open its full solution, or practise it on an original problem with graded tests.
01Pattern
Two Pointers
Converge from both ends to compare characters without extra space.
O(n)naïve O(n²)When to reach for it
- Utilize two pointers when the problem involves searching for pairs or triplets of characters within a string that satisfy specific conditions, particularly in sorted strings or when the order matters.
Spot it in the prompt
Look for problem descriptions mentioning the need to compare characters from both ends of the string or to traverse the string simultaneously with two pointers. Phrases like 'pair of characters,' 'triplet of characters,' or 'sorted string' indicate the potential application of two pointers.
Valid Palindrome
How to solve it
Animation shows the Two Pointers techniqueSet pointers at both ends, skip non-alphanumeric characters, and compare mirrored letters case-insensitively until the pointers cross.
Mirror Phrase Check is our own problem on the same technique: a new statement, graded in your browser.
02Pattern
Sliding Window
A stretchy window scans substrings in one linear pass.
O(n)naïve O(n²)When to reach for it
- Apply the sliding window technique when you need to find a contiguous substring within the string with specific properties (e.g., maximum sum, minimum size, longest length) and you can adjust the window size dynamically as you traverse the string.
Spot it in the prompt
Problems involving contiguous substrings often hint at the use of the sliding window technique. Look for phrases like 'substring,' 'contiguous characters,' 'sliding window,' or hints that a window needs to slide through the string.
Minimum Window Substring
How to solve it
Animation shows the Sliding Window techniqueExpand the right edge until all target counts are covered, then shrink the left edge to minimize the still-valid window.
Shortest Kit Stretch is our own problem on the same technique: a new statement, graded in your browser.
03Pattern
Hashmaps
Count and look up characters in constant time.
O(n)When to reach for it
- Employ hashmaps when the problem involves frequency counting, grouping characters based on some property, or checking for the existence of certain characters in the string. Hashmaps offer efficient storage and retrieval of characters by keys.
Spot it in the prompt
Phrases like 'count,' 'frequency,' 'group,' or 'exist' suggest the potential use of hashmaps. Problems requiring counting occurrences, grouping similar characters, or checking for the presence of specific characters often indicate the application of hashmaps.
Group Anagrams
How to solve it
Animation shows the Hashmaps techniqueUse a sorted-character or frequency-count signature as the map key, bucketing every string that shares the same signature.
Bin Label Families is our own problem on the same technique: a new statement, graded in your browser.
04Pattern
String Manipulation
Reverse, parse, and rebuild strings character by character.
When to reach for it
- Utilize string manipulation techniques when tasked with operations such as reversing, splitting, joining, or converting strings into different formats. These techniques are useful for parsing input, formatting output, or transforming strings according to specific rules.
Spot it in the prompt
Problem descriptions mentioning operations like 'manipulate,' 'convert,' 'parse,' or specific string operations (e.g., reversing, splitting) indicate the need for string manipulation techniques.
Reverse String
How to solve it
Animation shows the String Manipulation techniqueSwap characters from both ends inward, mutating the character array in place until the pointers meet.
Flip the Stamp Strip is our own problem on the same technique: a new statement, graded in your browser.
05Pattern
Regular Expressions
Match text against patterns with wildcards and DP.
O(n·m)When to reach for it
- Apply regular expressions when the problem involves pattern matching or string validation based on specific rules, especially complex patterns or constraints. Regular expressions provide a powerful way to search, validate, and manipulate text efficiently.
Spot it in the prompt
Look for phrases like 'pattern,' 'validation,' 'matching,' or specific patterns (e.g., email addresses, phone numbers). Problems requiring validation of input strings against specific patterns or constraints often suggest the application of regular expressions.
Regular Expression Matching
How to solve it
Animation shows the Regular Expressions techniqueFill a DP table over string and pattern indices, treating '*' as zero-or-more of its preceding element.
Mask Matches The Whole Code is our own problem on the same technique: a new statement, graded in your browser.
After the pattern
Now solve one you haven't seen.
Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.
1,194 problems · 15,062 graded tests · free