45:"/_next/static/chunks/33yus346z0l_n.js" 46:"/_next/static/chunks/2j22cxchii_xx.js" 47:"/_next/static/chunks/0iv56yrji_20j.js" 48:"/_next/static/chunks/32izpn90gvm22.js" 49:"/_next/static/chunks/3j8bi-zu9bqs4.js" 4a:"/_next/static/chunks/1z-pox7hqp2x3.js" 4b:"/_next/static/chunks/20w4eaqlekefm.js" 4c:"/_next/static/chunks/1tn-0fivsxsv1.js" 4d:"/_next/static/chunks/09nq57stwzkgf.js" 4e:"/_next/static/chunks/3m1xjj5kw5fie.js" 4f:"/_next/static/chunks/0gafyzg9j9yqj.js" 50:"/_next/static/chunks/3k2gyg36fnag_.js" 51:"/_next/static/chunks/3bgoyiso1rhn7.js" 52:"/_next/static/chunks/3cstd6xzfli_o.js" 53:"/_next/static/chunks/253gnmj0-cj17.js" 54:"/_next/static/chunks/0hlb44ca7-4a2.js" 55:"/_next/static/chunks/20329i6m_04t6.js" 56:"/_next/static/chunks/40mq7ggq-ozo4.js" 57:"/_next/static/chunks/082jo-0ajazgr.js" 58:"/_next/static/chunks/2ozcrjb_hh74t.js" 59:"/_next/static/chunks/01a-3hvnqu8wl.js" 5a:"/_next/static/chunks/05i8en-x14ibi.js" 5b:"/_next/static/chunks/3m0r7x0jt5wm7.js" 5c:"/_next/static/chunks/2k8pepwc4pxns.js" 5d:"/_next/static/chunks/0wa9m1-tphf9u.js" 5e:"/_next/static/chunks/30jdm3dwz834g.js" 5f:"/_next/static/chunks/0k9bl6dipnsvu.js" 60:"/_next/static/chunks/18ggtgz2yf759.js" 61:"/_next/static/chunks/0i3-eynrkvqi7.js" 62:I[593304,["$2a","$2b","$2c","$2d","$2e","$2f","$45","$46","$47","$48","$49","$4a","$4b","$4c","$4d","$4e","$4f","$50","$51","$52","$53","$54","$55","$56","$57","$58","$59","$5a","$5b","$5c","$5d","$5e","$5f","$60","$61"],"OwnedHydration"] 63:T458,function stringCompare(s1: string, s2: string): number { /** * Compare two strings character by character. * Returns: -1 if s1 < s2, 0 if s1 == s2, 1 if s1 > s2 * * Time Complexity: O(min(s1.length, s2.length)) * - Best case: O(1) if first characters differ * - Worst case: O(m) where m = min(s1.length, s2.length) */ const minLen = Math.min(s1.length, s2.length); // Character-by-character comparison for (let i = 0; i < minLen; i++) { if (s1[i] < s2[i]) { return -1; } else if (s1[i] > s2[i]) { return 1; } } // All compared characters match; shorter string is "less" if (s1.length < s2.length) { return -1; } else if (s1.length > s2.length) { return 1; } return 0; } // Demonstration: comparing similar strings console.log("Comparing 'algorithm' vs 'algorithmic':"); console.log(" Must compare 9 characters before finding difference"); console.log(" Comparing 'apple' vs 'zebra':"); console.log(" Only 1 character comparison needed (first chars differ)");64:T531,public class StringComparison { /** * Compare two strings character by character. * Returns: -1 if s1 < s2, 0 if s1 == s2, 1 if s1 > s2 * * Time Complexity: O(min(s1.length(), s2.length())) * - Best case: O(1) if first characters differ * - Worst case: O(m) where m = min(s1.length(), s2.length()) */ public static int stringCompare(String s1, String s2) { int minLen = Math.min(s1.length(), s2.length()); // Character-by-character comparison for (int i = 0; i < minLen; i++) { if (s1.charAt(i) < s2.charAt(i)) { return -1; } else if (s1.charAt(i) > s2.charAt(i)) { return 1; } } // All compared characters match; shorter string is "less" if (s1.length() < s2.length()) { return -1; } else if (s1.length() > s2.length()) { return 1; } return 0; } public static void main(String[] args) { System.out.println("Comparing 'algorithm' vs 'algorithmic':"); System.out.println(" Must compare 9 characters before finding difference"); System.out.println(" Comparing 'apple' vs 'zebra':"); System.out.println(" Only 1 character comparison needed"); } }65:T55d,class NaiveStringCollection: """ Simplest possible string collection: unsorted list. Operations: - Insert: O(1) amortized (append to end) - Search: O(n × m) where n = collection size, m = string length - Delete: O(n × m) (find then remove) """ def __init__(self): self.strings: list[str] = [] def insert(self, s: str) -> None: """Add string to collection. O(1) amortized.""" self.strings.append(s) def search(self, target: str) -> bool: """ Check if target exists in collection. O(n × m) time: must potentially scan all strings, and each comparison costs O(m). """ for s in self.strings: if s == target: # This is O(m) per comparison! return True return False def find_all_matching(self, target: str) -> list[int]: """Return indices of all matching strings.""" result = [] for i, s in enumerate(self.strings): if s == target: result.append(i) return result # Analysis at scale collection = NaiveStringCollection() # Imagine 100,000 strings, average length 20 characters # To search for "nonexistent_string_xyz": # - Check all 100,000 strings # - Each check compares up to 20 characters # - Total: up to 2,000,000 character comparisons!66:T5d5,class NaiveStringCollection { /** * Simplest possible string collection: unsorted array. * * Operations: * - Insert: O(1) amortized (push to end) * - Search: O(n × m) where n = collection size, m = string length * - Delete: O(n × m) (find then remove) */ private strings: string[] = []; insert(s: string): void { // Add string to collection. O(1) amortized. this.strings.push(s); } search(target: string): boolean { /** * Check if target exists in collection. * O(n × m) time: must potentially scan all strings, * and each comparison costs O(m). */ for (const s of this.strings) { if (s === target) { // This is O(m) per comparison! return true; } } return false; } findAllMatching(target: string): number[] { // Return indices of all matching strings. const result: number[] = []; for (let i = 0; i < this.strings.length; i++) { if (this.strings[i] === target) { result.append(i); } } return result; } } // Analysis at scale const collection = new NaiveStringCollection(); // Imagine 100,000 strings, average length 20 characters // To search for "nonexistent_string_xyz": // - Check all 100,000 strings // - Each check compares up to 20 characters // - Total: up to 2,000,000 character comparisons!67:T7b3,import bisect class SortedStringCollection: """ Sorted string collection with binary search. Operations: - Insert: O(n) (maintain sorted order via insertion) - Search: O(m × log n) using binary search - Delete: O(n) (find then shift elements) """ def __init__(self): self.strings: list[str] = [] # Kept in sorted order def insert(self, s: str) -> None: """ Add string maintaining sorted order. O(n) time due to shifting elements after insertion point. """ # bisect.insort uses binary search for position: O(m × log n) # Then shifts elements: O(n) bisect.insort(self.strings, s) def search(self, target: str) -> bool: """ Binary search for target. O(m × log n) time: - O(log n) binary search iterations - Each iteration: one string comparison = O(m) """ if not self.strings: return False left, right = 0, len(self.strings) - 1 while left <= right: mid = (left + right) // 2 comparison = self._compare(self.strings[mid], target) if comparison == 0: return True # Found elif comparison < 0: left = mid + 1 # Target is in right half else: right = mid - 1 # Target is in left half return False def _compare(self, s1: str, s2: str) -> int: """Compare strings. Returns -1, 0, or 1. Takes O(m) time.""" if s1 < s2: return -1 if s1 > s2: return 1 return 0 # This is much better than linear search! # For n = 100,000 strings of length m = 20: # - Linear: O(n × m) = 2,000,000 operations worst case # - Binary: O(m × log n) = 20 × 17 ≈ 340 operations worst case # # But we pay for this at insertion time: O(n) per insert # And prefix queries? Still problematic...68:T4f3,def naive_prefix_search(collection: list[str], prefix: str) -> list[str]: """ Find all strings starting with the given prefix. Time Complexity: O(n × m) - n = size of collection - m = length of prefix being checked For 10 million strings with prefix "pro" (length 3): - Must check all 10,000,000 strings - Each check: compare first 3 characters - Total: up to 30,000,000 character comparisons - At 1 billion comparisons/second: 30ms just for matching - Plus memory bandwidth, cache misses, etc. """ matches = [] for s in collection: if s.startswith(prefix): # O(len(prefix)) per check matches.append(s) return matches # This approach has fundamental problems: # 1. LINEAR in collection size - doesn't matter how short the prefix is # 2. Must scan ENTIRE collection even to find ZERO matches # 3. No way to "skip" irrelevant strings # 4. Memory access pattern is terrible for caching # Real numbers for a production system: # - 10 million strings # - Average 20 characters each # - User types "pro": scan all 10M strings # - User types "prog": scan all 10M strings AGAIN # - User types "progr": scan all 10M strings AGAIN # # Each keystroke triggers a full collection scan!69:T69a,import bisect def sorted_prefix_search(sorted_collection: list[str], prefix: str) -> list[str]: """ Find all strings starting with prefix in a sorted collection. Strategy: Binary search for the range of matching strings. Time Complexity: O(m × log n + k × m) - m = prefix length - n = collection size - k = number of matches Better than naive for small k, but still problematic. """ if not sorted_collection: return [] # Find first position where prefix could appear # "pro" would find first string >= "pro" left_idx = bisect.bisect_left(sorted_collection, prefix) # Collect all strings starting with this prefix matches = [] for i in range(left_idx, len(sorted_collection)): s = sorted_collection[i] if s.startswith(prefix): # O(m) comparison matches.append(s) else: # Since collection is sorted, once we find a non-match, # all subsequent strings also won't match break return matches # This is much better! For "pro" with 10 million sorted strings: # - Binary search: ~24 iterations × 3 char comparisons = 72 operations # - Then scan matches: if 50,000 strings start with "pro", # that's ~150,000 character comparisons # # Total: ~150,000 vs naive's 30,000,000 - a 200x improvement! # But there are still issues: # 1. Insertions are O(n) - terrible for dynamic collections # 2. The O(k × m) term can dominate for popular prefixes # 3. Memory locality is poor - strings are scattered in memory # 4. No incremental benefit from previous searches # (typing "pro" then "prog" restarts from scratch)6a:T43c,**The constraints that shape our solutions:** **1. Latency Budget** Users perceive responses under 100ms as 'instant'. Above 300ms, they notice delay. Above 1 second, they become frustrated. For interactive features like autocomplete, we typically have 50ms or less to: - Receive the query - Search the collection - Rank results - Format and transmit response The actual search operation might have only 10-20ms of this budget. **2. Throughput Requirements** A single user might generate 10-20 prefix queries while typing one search (one per keystroke with debouncing). Multiply by concurrent users: - 1,000 concurrent users = 10,000-20,000 queries/second - 100,000 concurrent users = 1-2 million queries/second Each query must complete within the latency budget. **3. Memory Constraints** Storing billions of strings efficiently requires careful memory management: - Raw storage: 10 billion strings × 20 chars × 2 bytes/char = 400 GB - With per-string overhead (length, pointer, etc.): easily 600+ GB - Fitting this in RAM requires compression or accepting disk I/O latency6b:T491,Imagine representing these words as a tree where shared prefixes share nodes: ``` (root) | 'p' | 'r' | 'o' / 'g' 'j' | | 'r' 'e' /| | 'a' 'e' 'c' | | | 'm' 's' 't' → "project" / | | ● ● ● → "progress" / | 'm' ● → "program" | 'i' | 'n' | 'g' | ● → "programming", "programmer" ``` Now, searching for 'programming': 1. Navigate: p → r → o → g → r → a → m → m → i → n → g 2. **11 character lookups total** — not 37! 3. Each character is processed **exactly once**, regardless of collection size This is the trie insight: **represent the collection as a tree where each path from root to a marked node represents a word, and shared prefixes share their paths.**43:["$","$L62",null,{"owner":"anonymous","state":{"mutations":[],"queries":[{"dehydratedAt":1792296542973,"state":{"data":{"json":{"id":"seed_78365e86f6a7dfda625aab71b04d54bf","slug":"string-search-problems","category":"Data Structures & Algorithms","topic":"String Search Problems — Motivation for Tries","title":"String Search Problems — Motivation for Tries","description":"Explore the fundamental challenges of searching strings in collections. Understand why traditional data structures struggle with prefix matching and string-specific operations, building the foundation for understanding tries as the elegant solution.","difficulty":"INTERMEDIATE","estimatedMinutes":60,"pages":[{"id":"seed_e97038c2abb104080ccc035da785363d","title":"Searching for Strings in a Collection","order":0,"content":[{"id":"opening-hook","title":"The Ubiquity of String Search","content":[{"data":{"content":"Every time you type a search query, every time your IDE suggests a function name, every time a spell checker flags a typo, every time an autocomplete dropdown appears—behind the scenes, sophisticated string search algorithms are racing against time to find matches in potentially massive collections of strings.\n\n**String search is fundamentally different from numeric search.** When searching for a number, comparison is instant: is 42 greater than, equal to, or less than 100? The answer emerges in a single CPU operation. But strings introduce layers of complexity that transform an apparently simple problem into one of the most studied areas in computer science."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand the fundamental challenges of string search: why comparing strings is inherently expensive, how collection size impacts performance, the crucial distinction between exact and prefix matching, and why understanding these problems is essential before learning about tries.","variant":"info"},"type":"callout"}]},{"id":"string-comparison-problem","title":"The String Comparison Problem","content":[{"data":{"content":"To appreciate why string search requires specialized data structures, we must first understand why string comparison itself is expensive.\n\n**Integers compare in O(1) time.** Modern CPUs have dedicated instructions for comparing 32-bit or 64-bit integers. A comparison like `42 < 100` executes in a single clock cycle—it's as fast as anything can be.\n\n**Strings compare in O(m) time**, where m is the length of the shorter string. To determine if \"algorithm\" equals \"algorithmic\", we must compare character by character: a=a, l=l, g=g, o=o, r=r, i=i, t=t, h=h, m=m, and only then discover that one string continues while the other ends."},"type":"text"},{"data":{"fileName":"String Comparison Analysis","languages":[{"code":"def string_compare(s1: str, s2: str) -> int:\n \"\"\"\n Compare two strings character by character.\n Returns: -1 if s1 < s2, 0 if s1 == s2, 1 if s1 > s2\n \n Time Complexity: O(min(len(s1), len(s2)))\n - Best case: O(1) if first characters differ\n - Worst case: O(m) where m = min(len(s1), len(s2))\n \"\"\"\n min_len = min(len(s1), len(s2))\n \n # Character-by-character comparison\n for i in range(min_len):\n if s1[i] < s2[i]:\n return -1\n elif s1[i] > s2[i]:\n return 1\n \n # All compared characters match; shorter string is \"less\"\n if len(s1) < len(s2):\n return -1\n elif len(s1) > len(s2):\n return 1\n return 0\n\n# Demonstration: comparing similar strings\nprint(f\"Comparing 'algorithm' vs 'algorithmic':\")\nprint(f\" Must compare 9 characters before finding difference\")\n\nprint(f\"\nComparing 'apple' vs 'zebra':\")\nprint(f\" Only 1 character comparison needed (first chars differ)\")","label":"Python","value":"python"},{"code":"$63","label":"TypeScript","value":"typescript"},{"code":"$64","label":"Java","value":"java"}],"showLineNumbers":true},"type":"code"},{"data":{"icon":"AlertCircle","title":"The Hidden Cost Multiplier","content":"When analyzing string algorithms, the O(m) comparison cost often gets absorbed into complexity analysis, but it's crucial to remember: every 'single comparison' in a string algorithm actually costs O(m) time where m is the string length. A binary search on n sorted strings isn't O(log n)—it's O(m log n).","variant":"warning"},"type":"callout"},{"data":{"content":"**The implications are profound:**\n\nImagine searching a dictionary of 100,000 English words with average length 8 characters. Using sorted array with binary search:\n\n- **For integers:** ~17 comparisons × O(1) each = **O(17)** operations\n- **For strings:** ~17 comparisons × O(8) each = **O(136)** character operations\n\nThis 8x multiplier compounds at scale. For a database of 1 million URLs averaging 50 characters:\n\n- **For integers:** ~20 comparisons × O(1) each = **O(20)** operations \n- **For strings:** ~20 comparisons × O(50) each = **O(1000)** character operations\n\nThe string search problem isn't just 'search but with strings'—it's a fundamentally different challenge requiring fundamentally different solutions."},"type":"text"}],"titleType":"number","titleNumber":1},{"id":"naive-approaches","title":"Naive Approaches and Their Limits","content":[{"data":{"content":"Let's examine the most straightforward approaches to searching for a string in a collection, understanding precisely where and why they fail.\n\n**Approach 1: Unsorted Array with Linear Search**\n\nStore all strings in an array and scan through each one when searching."},"type":"text"},{"data":{"fileName":"Linear Search Implementation","languages":[{"code":"$65","label":"Python","value":"python"},{"code":"$66","label":"TypeScript","value":"typescript"}],"showLineNumbers":true},"type":"code"},{"data":{"content":"**Approach 2: Sorted Array with Binary Search**\n\nSort the strings lexicographically and use binary search to locate targets."},"type":"text"},{"data":{"fileName":"Binary Search on Sorted Strings","languages":[{"code":"$67","label":"Python","value":"python"}],"showLineNumbers":true},"type":"code"},{"data":{"rows":[["Insert","O(1) amortized","O(n)","Sorted requires maintaining order"],["Search (exact)","O(n × m)","O(m × log n)","m = string length, n = collection size"],["Delete","O(n × m)","O(n × m)","Both require finding then removing"],["Prefix Search","O(n × m)","O(m × log n + k × m)","k = number of matches; both are inefficient"],["Autocomplete","O(n × m)","O(m × log n + k × m)","Getting ALL matches is expensive"]],"caption":"Comparison of Naive String Collection Approaches","headers":["Operation","Unsorted Array","Sorted Array","Notes"]},"type":"table"},{"data":{"icon":"Lightbulb","title":"The Key Insight","content":"Binary search dramatically improves exact match search, but notice something crucial: the string length m remains a multiplicative factor. Unlike integers where each comparison is O(1), string comparisons read character by character. This inherent cost motivates us to look for structures that can avoid repeated character comparisons.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"string-search-types","title":"Types of String Search Problems","content":[{"data":{"content":"Before we can design better solutions, we must precisely define what 'string search' means. The term encompasses several distinct problems, each with different requirements and optimal solutions.\n\n**The taxonomy of string search problems:**"},"type":"text"},{"data":{"items":["**Exact Match** — Does the string 'apple' exist in our collection? Return yes/no or the location.","**Prefix Match** — Find all strings that START with 'app' (e.g., 'apple', 'application', 'appetite'). This is what autocomplete systems need.","**Suffix Match** — Find all strings that END with 'tion' (e.g., 'application', 'attention'). Used in reverse dictionaries and rhyming systems.","**Substring Match** — Find all strings that CONTAIN 'cat' anywhere (e.g., 'catalog', 'concatenate', 'scat'). Used in full-text search.","**Pattern Match** — Find all strings matching a pattern like 'a*b' or '[abc]d+'. Regular expression engines solve this.","**Fuzzy Match** — Find strings SIMILAR to 'apple' allowing for typos (e.g., 'appel', 'aple'). Spell checkers and search engines need this."],"title":{"icon":"Target","text":"String Search Problem Categories","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**Each problem type demands different data structures:**\n\nWe'll discover that **tries excel at prefix matching** — the exact problem that arises in autocomplete, dictionary suggestions, IP routing, and many other applications. Other problem types may require different structures:\n\n- **Exact match:** Hash tables offer O(m) average time\n- **Suffix match:** Suffix trees or suffix arrays\n- **Substring match:** Full-text indexes, suffix arrays\n- **Pattern match:** Finite automata, regex engines\n- **Fuzzy match:** BK-trees, Levenshtein automata, edit distance algorithms\n\nThis chapter focuses on **prefix matching** because it's both incredibly common and because the trie provides an elegant, generalizable solution."},"type":"text"},{"data":{"left":[{"data":{"items":["Query: 'pro' → 'program', 'promise', 'project', 'process'","Query: 'auto' → 'autocomplete', 'automatic', 'automobile'","Query: 'inter' → 'interface', 'internet', 'internal', 'interpret'","Query: 'data' → 'database', 'datatype', 'dataset', 'datacenter'"],"title":{"icon":"CheckCircle","text":"Prefix Match Examples","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["'cat' matching 'concatenate' (substring, not prefix)","'tion' matching 'function' (suffix, not prefix)","'file' matching 'profile' (suffix-like, not prefix)","'net' matching 'internet' (substring in middle)"],"title":{"icon":"XCircle","text":"NOT Prefix Matches","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"}],"titleType":"number","titleNumber":3},{"id":"prefix-matching-challenge","title":"The Prefix Matching Challenge","content":[{"data":{"content":"Let's dig deeper into why prefix matching is particularly challenging for traditional data structures.\n\n**The Autocomplete Scenario:**\n\nImagine building an autocomplete system for a search engine. You have 10 million common search queries stored. As the user types each character, you need to:\n\n1. Find all queries that start with the typed prefix\n2. Rank them by popularity\n3. Return the top 10 suggestions\n4. Do this in under 100 milliseconds\n5. Handle thousands of users simultaneously\n\nWith a naive approach, here's what happens when a user types 'pro':"},"type":"text"},{"data":{"fileName":"Naive Prefix Search","languages":[{"code":"$68","label":"Python","value":"python"}],"showLineNumbers":true},"type":"code"},{"data":{"content":"**Can sorted arrays help with prefix search?**\n\nYes, but only partially. With a sorted array, we can use binary search to find the *first* string with the prefix, then scan forward to find all matches:"},"type":"text"},{"data":{"fileName":"Binary Search for Prefix Range","languages":[{"code":"$69","label":"Python","value":"python"}],"showLineNumbers":true},"type":"code"},{"data":{"icon":"Info","title":"The Fundamental Limitation","content":"Even with sorted arrays, we're limited by the structure of the data itself. Strings with common prefixes are stored separately, so finding all matches requires visiting each one individually. What if we could store strings in a way that shares their common prefixes, so processing 'pro' once automatically includes all words starting with 'pro'?","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"real-world-scale","title":"Real-World Scale and Constraints","content":[{"data":{"content":"Understanding string search at scale requires appreciating the actual numbers involved in production systems:\n\n**Consider these real-world scenarios:**"},"type":"text"},{"data":{"rows":[["Search Engine Autocomplete","1-10 billion queries","Millions/second","< 50ms"],["IDE Code Completion","100K-1M symbols","10-100/second (per user)","< 50ms"],["DNS Lookup","~350 million domains","Billions/day globally","< 5ms"],["Spell Checker","100K-500K words","Continuous as user types","< 10ms"],["IP Routing Tables","~900K prefixes","Millions/second per router","< 1μs"],["Contact List Search","100-10K contacts","As user types","< 100ms"],["E-commerce Product Search","1-100 million products","Thousands/second","< 100ms"]],"caption":"String Collections at Scale","headers":["Application","Collection Size","Query Frequency","Latency Requirement"]},"type":"table"},{"data":{"content":"$6a"},"type":"text"},{"data":{"icon":"AlertCircle","title":"The Performance Cliff","content":"Many systems work fine until they hit a certain scale, then fail catastrophically. A naive O(n) approach that works for 10,000 strings fails utterly at 10 million. Understanding algorithmic complexity isn't academic—it's the difference between systems that scale and systems that collapse.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"shared-prefix-observation","title":"The Shared Prefix Observation","content":[{"data":{"content":"Here's the key insight that will lead us to tries: **strings with common prefixes are performing redundant comparisons.**\n\nConsider searching for 'programming' in a collection containing:\n- 'program'\n- 'programmer'\n- 'programming'\n- 'progress'\n- 'project'\n\nWith naive comparison, we compare 'programming' against each:\n\n```\n'programming' vs 'program' - compare 7 chars, find difference at position 8\n'programming' vs 'programmer' - compare 10 chars, find difference at position 11 \n'programming' vs 'programming' - compare 11 chars, match!\n'programming' vs 'progress' - compare 5 chars, find difference at position 5\n'programming' vs 'project' - compare 4 chars, find difference at position 4\n```\n\n**Total: 37 character comparisons.**\n\nBut notice: we compared 'pro' four times! 'prog' twice! 'program' twice!\n\n**What if we shared these common prefixes in our data structure?**"},"type":"text"},{"data":{"content":"$6b"},"type":"text"},{"data":{"icon":"Sparkles","title":"The Trie Promise","content":"A trie achieves O(m) search time where m is the length of the search string—completely independent of n, the collection size! Whether your dictionary has 100 words or 100 million, searching for 'programming' takes exactly 11 character operations.","variant":"success"},"type":"callout"},{"data":{"content":"**But the benefits extend beyond search time:**\n\n**Prefix queries become trivial:**\n- Navigate to the prefix node\n- All descendants are strings with that prefix\n- No scanning required—we've already arrived at exactly the right subtree\n\n**Common prefix = Shared storage:**\n- Instead of storing 'program', 'programmer', 'programming' separately (~30 chars)\n- We store the shared path once + branching extensions (~18 chars)\n- For dictionaries with highly shared prefixes (URLs, file paths, words), savings are dramatic\n\n**Incremental benefits compound:**\n- After searching 'pro', we're positioned to quickly extend to 'prog', 'prot', 'prom'\n- Each keystroke in autocomplete navigates one level deeper—O(1) per keystroke!\n\nThis chapter will build up to tries as the elegant solution to these problems. But first, we need to understand one more challenge: why can't hash tables solve this?"},"type":"text"}],"titleType":"number","titleNumber":6},{"id":"summary-whats-next","title":"Summary: The String Search Challenge","content":[{"data":{"content":"We've established a comprehensive understanding of why string search is fundamentally challenging and why naive approaches are inadequate for real-world applications."},"type":"text"},{"data":{"type":"ordered","items":["**String comparison is O(m), not O(1)** — This hidden cost multiplies through all string algorithms and must be accounted for in complexity analysis.","**Naive linear search is O(n × m)** — Scanning all strings in a collection is prohibitively expensive at scale.","**Sorted arrays improve exact search to O(m log n)** — But insertions become O(n) and prefix search still requires scanning matches.","**Prefix matching has unique characteristics** — It's a distinct problem from exact matching, substring matching, or fuzzy matching, and has its own optimal solutions.","**Real-world constraints are demanding** — Millisecond latencies, millions of queries/second, and massive collections require specialized data structures.","**Shared prefixes create optimization opportunities** — When strings share common beginnings, storing and processing them separately is wasteful."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's Next:**\n\nIn the next page, we'll dive deeper into the specific requirements of prefix matching and why it's such a critical operation in practice. We'll explore the applications that depend on efficient prefix queries and establish the precise requirements that our ideal data structure must satisfy.\n\nFrom there, we'll examine why hash tables—despite their excellent average-case performance for exact matching—fail to address prefix-based queries. This will set the stage for introducing the trie as the elegant solution to these challenges."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now understand the fundamental challenges of string search: the inherent cost of string comparison, the limitations of naive approaches, the various types of string search problems, and the key insight that shared prefixes create optimization opportunities. Next, we'll explore why prefix matching specifically is so important and common.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":7}],"isLocked":false},{"id":"seed_c3de5c83d4c73e290166df5ac918cd86","title":"Prefix Matching Requirements","order":1,"content":null,"isLocked":true},{"id":"seed_70bcc5eec951270d45d383577f84eb75","title":"Limitations of Hash Tables for Prefix Queries","order":2,"content":null,"isLocked":true},{"id":"seed_fee5d369bddaade3a35aa80fdb46a24e","title":"Why a Specialized Structure Helps","order":3,"content":null,"isLocked":true}]}},"dataUpdateCount":1,"dataUpdatedAt":1792296542970,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getModule"],{"input":{"slug":"string-search-problems"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getModule\"],{\"input\":{\"slug\":\"string-search-problems\"},\"type\":\"query\"}]"},{"dehydratedAt":1792296542973,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792296542969,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getProgress"],{"input":{"moduleId":"seed_78365e86f6a7dfda625aab71b04d54bf"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getProgress\"],{\"input\":{\"moduleId\":\"seed_78365e86f6a7dfda625aab71b04d54bf\"},\"type\":\"query\"}]"},{"dehydratedAt":1792296542973,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792296542969,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","get"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_c3de5c83d4c73e290166df5ac918cd86"},"type":"query"}],"queryHash":"[[\"feedback\",\"get\"],{\"input\":{\"contentId\":\"seed_c3de5c83d4c73e290166df5ac918cd86\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792296542973,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792296542969,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","getUserLike"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_c3de5c83d4c73e290166df5ac918cd86"},"type":"query"}],"queryHash":"[[\"feedback\",\"getUserLike\"],{\"input\":{\"contentId\":\"seed_c3de5c83d4c73e290166df5ac918cd86\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792296542973,"state":{"data":{"json":[]},"dataUpdateCount":1,"dataUpdatedAt":1792296542969,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["highlights","getHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_c3de5c83d4c73e290166df5ac918cd86"},"type":"query"}],"queryHash":"[[\"highlights\",\"getHighlights\"],{\"input\":{\"contentId\":\"seed_c3de5c83d4c73e290166df5ac918cd86\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792296542973,"state":{"data":"$undefined","dataUpdateCount":0,"dataUpdatedAt":0,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"pending","fetchStatus":"fetching"},"queryKey":[["highlights","getPopularHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_c3de5c83d4c73e290166df5ac918cd86","minCount":2},"type":"query"}],"queryHash":"[[\"highlights\",\"getPopularHighlights\"],{\"input\":{\"contentId\":\"seed_c3de5c83d4c73e290166df5ac918cd86\",\"contentType\":\"LEARNING_PAGE\",\"minCount\":2},\"type\":\"query\"}]","promise":"$@6c"}]},"children":"$L6d"}]