Strings Practice & Revision

1. Introduction

What is Strings Practice & Revision?

This lesson synthesizes all string representations, manipulations, and core algorithmic patterns into a unified String Pattern Recognition Framework.

Why is it Important?

String questions are notoriously deceptive: brute force solutions involving string slicing or nested loops quickly time out (O(N²) / O(N³)). A structured decision tree lets you pick the optimal O(N) or O(N log N) algorithm within the first 3 minutes of an interview.

Where is it Used?

Technical Coding Interviews: Solving String challenges at FAANG, Unicorns, and Top Tech firms.

Production Performance Tuning: Avoiding hidden string allocation overhead in web backend servers.

---

2. Mental Model

Think of string pattern recognition as a Diagnostic Decision Flowchart.

---

3. Concept: The String Pattern Decision Tree

Follow this exact decision workflow when presented with any string problem:

---

4. Visuals

Pattern Recognition Map

---

5. Real-World Examples

High-Throughput Log Parsing: Using character arrays and custom index pointers instead of regex to parse millions of HTTP request headers in real time.

Search Engine Query Suggestion: Combining Trie prefix matching with frequency priority queues (Min-Heaps) to serve top-5 autocomplete suggestions in under 10ms.

---

6. Interview Perspective

5-Step String Strategy

1. Clarify Character Set (1 min): Ask: "Is the string ASCII only? Lowercase English ('a'-'z') or Unicode?" 2. Beware Immutability (2 min): In Java/Python, state that you will use a StringBuilder or list of characters to avoid O(N²) concatenation costs. 3. Select Optimal Pattern (3 min): State why Frequency Array / Two Pointers / Sliding Window / KMP / Trie eliminates unnecessary sub-string copy passes. 4. Code Cleanly (10 min): Write modular code with clear variable names (left, right, charCount, isEndOfWord). 5. Dry-Run Edge Cases (4 min): Test empty strings "", single-character strings "a", and strings with no matching pattern.

---

7. Summary & Revision Cheat Sheet

---

8. Quiz

Question 1: What is the optimal time and space complexity to group a list of N strings of length L into anagram buckets?

Answer: O(N × L) time and O(N × L) space using a size-26 frequency tuple as the HashMap key.

Question 2: Why is string concatenation using += inside a loop an antipattern in Java and Python?

Answer: Because strings are immutable. Each += allocates a new string object and copies all previous characters, resulting in O(N²) overall runtime.

Question 3: When should you use a Trie over a HashSet for string lookups?

Answer: Use a Trie when you need prefix matching (startsWith()), autocomplete suggestions, or shared prefix memory savings across millions of words.

Question 4: How does KMP achieve O(N + M) time complexity for substring matching?

Answer: By precomputing an O(M) LPS (Longest Prefix Suffix) table that lets the pattern pointer skip redundant comparisons without ever moving the text pointer backward.

Question 5: How do you handle even-length vs odd-length palindromes when expanding around a center?

Answer: For odd-length palindromes, expand around single character centers (i, i). For even-length palindromes, expand around adjacent character centers (i, i+1).