dsa2 min read
Word Ladder — BFS Shortest Transformation
Find minimum transformations from beginWord to endWord changing one letter at a time (each intermediate must be in wordList). Classic BFS on word states.
Read →
String
22 articles
dsa1 min read
Most Common Word — Normalize + Frequency Map
Find the most common word not in a banned list by normalizing input and using a frequency counter.
Read →
dsa2 min read
Palindrome Pairs — HashMap + Palindrome Check
Find all index pairs forming palindromes by checking prefix/suffix splits against a reverse-word map.
Read →
dsa1 min read
Make the String Great — Stack Same-Letter Case Check
Remove adjacent pairs of same letters with different cases using a stack to build the result character by character.
Read →
dsa2 min read
Decode String — Stack for Counts and Strings
Decode a string with nested encodings like 3[a2[bc]] using two stacks: one for counts and one for partial strings.
Read →
dsa2 min read
Word Ladder — BFS Shortest Transformation Path
Find the shortest word transformation sequence using BFS where each step changes exactly one character.
Read →
dsa1 min read
Remove All Adjacent Duplicates in String II — Stack with Counts
Remove k adjacent identical characters repeatedly using a stack that tracks (character, count) pairs.
Read →
dsa2 min read
KMP Algorithm — O(n+m) Pattern Matching with Failure Function
Implement KMP string search: build the failure function (LPS array) in O(m) then search in O(n). Never re-examines matched characters unlike naive search.
Read →
dsa2 min read
Z-Algorithm — Linear Prefix Matching for All Positions
The Z-algorithm computes Z[i] = length of the longest substring starting at i that matches a prefix of the string. O(n) time, elegant and powerful for pattern search.
Read →
dsa2 min read
Rabin-Karp — Rolling Hash for Pattern Matching and Substring Search
Rabin-Karp uses a rolling polynomial hash to match patterns in O(n+m) expected time. The key is updating the hash in O(1) as the window slides.
Read →
dsa2 min read
Manacher's Algorithm — Longest Palindromic Substring in O(n)
Find the longest palindromic substring in O(n) using Manacher's algorithm. Expands palindromes using a mirror trick to avoid redundant work.
Read →
dsa2 min read
String DP — Edit Distance, LCS, and Interleaving
Core string DP patterns: edit distance (Wagner-Fischer), longest common subsequence, interleaving strings, and regular expression matching.
Read →
dsa2 min read
Anagram Problems — Sorting Key, Frequency Vector, and Rolling Hash
Group anagrams, find anagram indices, and count anagram occurrences. Three approaches: sort key O(nk log k), frequency tuple O(nk), and sliding window O(n+k).
Read →
dsa2 min read
Encode and Decode Strings — Delimiter and Length-Prefix Schemes
Design an encode/decode scheme for a list of strings. Length-prefix encoding (4-byte header per string) is collision-proof unlike delimiter-based approaches.
Read →
dsa2 min read
Shortest Palindrome — KMP on Reversed String
Add minimum characters to the front of a string to make it a palindrome. KMP trick: concatenate s + '#' + rev(s), find the LPS value at the last position.
Read →
dsa2 min read
String Compression and Run-Length Encoding
Implement run-length encoding, string compression in-place, and decode compressed strings. Tests two-pointer technique and string manipulation.
Read →
dsa2 min read
String Problems — Meta and Google Favourites
High-frequency string problems from Meta and Google interviews: valid parentheses, longest substring without repeating characters, zigzag conversion, and string to integer.
Read →
dsa2 min read
Google — Longest Substring with K Distinct Characters
Find the longest substring with at most k distinct characters using a sliding window with a character frequency map. O(n) time.
Read →
dsa2 min read
Meta — Generate Parentheses (Backtracking)
Generate all combinations of well-formed parentheses of given n pairs using backtracking. Track open and close counts to prune invalid branches early.
Read →
dsa2 min read
Google — Word Break II (DP + Backtracking with Memoisation)
Return all ways to segment a string into dictionary words. Combines DP validity check with DFS+memo backtracking to avoid TLE on valid inputs.
Read →
dsa2 min read
Meta — Accounts Merge (Union-Find on Emails)
Merge accounts sharing common email addresses using Union-Find. Group emails by owner, merge accounts with shared emails, sort each merged group.
Read →
dsa2 min read
Design Log Storage System — Timestamp Range Retrieval
Design a log storage system that retrieves log IDs within a timestamp range at a specified granularity (Year, Month, Day, Hour, Minute, Second).
Read →