Strings look deceptively simple. You index them. You slice them. You concatenate them. Yet string problems are among the most common places where candidates make subtle mistakes in coding interviews. Why? Because string problems are rarely just about strings. They are often about:

representation
indexing
boundary conditions
in-place transformation
numerical reasoning
recursion
parsing
hashing
complexity

That is the real lesson of Part 6 — Strings. The goal is not to memorize 13 string problems. The goal is to recognize the underlying patterns that allow you to solve unfamiliar problems.

A string problem is often an array problem + a representation problem + careful boundary handling.

The original Part 6 progresses through 13 problems, from string/integer conversion to base conversion, in-place transformations, recursion, parsing, encoding, and finally substring search using Rabin–Karp.

1. What Part 6 Is Really Teaching

Instead of memorizing individual solutions, build a mental pattern library. STRINGS │ ┌───────────────────┼───────────────────┐ │ │ │ ▼ ▼ ▼ Two Pointers Conversion Parsing │ │ │ ▼ ▼ ▼ Palindrome Base Conversion IP / Roman Reverse Words Integer ↔ String │ ▼ In-place Manipulation │ ├───────────────┐ ▼ ▼ Recursion Enumeration │ │ ▼ ▼ Phone Mnemonics Look-and-Say │ ▼ String Algorithms │ ▼ Rabin–Karp

These patterns are far more valuable than memorizing individual code snippets.

2. The First Python Rule: Strings Are Immutable

Before solving any string problem in Python, remember one fundamental fact: str

is immutable. For example: s = “hello” s[0] = “H”

This raises: TypeError

You cannot modify an individual character of a Python string. This becomes especially important when an interviewer asks:

“Can you solve this in-place?”

The answer should demonstrate language awareness. You can say:

“Python strings are immutable, so for true in-place character manipulation I would use a list of characters or a bytearray.”

This distinction is important because many textbook algorithms assume a mutable character array.

3. Be Careful With String Concatenation

Consider: result = “”

for ch in data: result += ch

Because strings are immutable, repeated concatenation can lead to quadratic behavior in the general model. A better approach is: result = []

for ch in data: result.append(ch)

return ‘’.join(result)

The general interview rule is:

Build pieces separately, then join them.

This is one of the most important Python-specific lessons in this Part.

4. String Operations You Should Know Cold

For interviews, these should become automatic: s[i] len(s)

s[a:b] s[::-1]

x in s

s.startswith(prefix) s.endswith(suffix)

s.lower() s.upper()

s.strip() s.split()

“ “.join(words)

s.find(pattern)

Also know: s.isalnum() s.isalpha() s.isdigit() s.isspace()

The important point isn’t memorizing syntax. It’s understanding the performance implications of the operations you’re choosing.

5. The 13 Problems in Part 6

The Part covers:

Problem	Core Concept
6.1	String ↔ Integer
6.2	Base Conversion
6.3	Spreadsheet Column Encoding
6.4	Replace and Remove
6.5	Palindrome
6.6	Reverse Words
6.7	Phone Mnemonics
6.8	Look-and-Say
6.9	Roman → Decimal
6.10	Valid IP Addresses
6.11	Sinusoidal String
6.12	Run-Length Encoding
6.13	Substring Search

The interesting part is how these apparently different problems collapse into a handful of reusable techniques.

6. String ↔ Integer: The Foundation

This is one of the most important problems in the Part. The task is to implement: integer → string string → integer

without simply using: str(x) int(s)

The deeper goal is understanding how positional representations work.

Integer → String

Suppose: 314

Extract the digits from right to left: 314 % 10 = 4 314 // 10 = 31

31 % 10 = 1 31 // 10 = 3

3 % 10 = 3

We obtain: 4 → 1 → 3

Reverse them: 3 → 1 → 4

Python: def int_to_string(x): negative = x < 0

if negative: x = -x

digits = []

if x == 0: return “0”

while x: digit = x % 10 digits.append(chr(ord(‘0’) + digit)) x //= 10

if negative: digits.append(‘-’)

return ‘’.join(reversed(digits))

Complexity: Time: O(n) Space: O(n)

where n is the number of digits.

7. String → Integer

Now reverse the problem. Given: “314”

Don’t explicitly calculate: 3 × 10² + 1 × 10¹ + 4

Instead use: result = result * 10 + digit

Step by step: result = 0

read 3: 0 × 10 + 3 = 3

read 1: 3 × 10 + 1 = 31

read 4: 31 × 10 + 4 = 314

Python: def string_to_int(s): negative = s[0] == ‘-’ start = 1 if negative else 0

result = 0

for i in range(start, len(s)): digit = ord(s[i]) - ord(‘0’) result = result * 10 + digit

return -result if negative else result

Complexity: Time: O(n) Space: O(1)

8. The Deeper Pattern: Horner’s Rule

This is where the problem becomes more interesting. The recurrence: result = result * base + digit

isn’t merely a trick for parsing strings. It is a general positional-number technique. It appears in:

number parsing
base conversion
polynomial evaluation
rolling hashes

And that final connection becomes extremely important later when we reach Rabin–Karp.

Interview takeaway

Whenever you see: digits + positional representation

think: accumulate → multiply by base → add digit

9. Base Conversion

Suppose we need to convert: 615₇

into base 13. The clean approach is: Base b₁ ↓ Integer ↓ Base b₂

First convert: 615₇

into decimal. Using the recurrence: 0 × 7 + 6 = 6 6 × 7 + 1 = 43 43 × 7 + 5 = 306

Therefore: 615₇ = 306₁₀

Now convert 306 to base 13. Repeated division: 306 % 13 = 7 306 // 13 = 23

23 % 13 = 10 → A 23 // 13 = 1

1 % 13 = 1

Reverse the digits: 1A7

Therefore: 615₇ = 1A7₁₃

The underlying patterns are: Base → Integer ↓ result = result * base + digit

Integer → Base ↓ digit = value % base value //= base

This is worth memorizing conceptually—not line by line.

10. Spreadsheet Column Encoding

Consider spreadsheet columns: A → 1 B → 2 … Z → 26 AA → 27 AB → 28 … ZZ → 702

At first glance, this looks like base 26. But there is a subtle difference. Normal base-26 digits are: A = 0 B = 1 … Z = 25

Spreadsheet encoding uses: A = 1 B = 2 … Z = 26

That one-based representation is the entire trick. Python: def spreadsheet_decode(col): result = 0

for c in col: value = ord(c) - ord(‘A’) + 1 result = result * 26 + value

return result

Examples: spreadsheet_decode(“D”) # 4

spreadsheet_decode(“AA”) # 27

spreadsheet_decode(“ZZ”) # 702

Complexity: Time: O(n) Space: O(1)

Interview insight

Whenever you see: A = 1 B = 2 …

ask yourself:

Is this actually a positional number system?

That question can unlock seemingly unrelated problems such as encoded identifiers and custom numbering systems.

11. Replace and Remove: The In-Place Transformation Pattern

This is one of the highest-value problems in the Part. Suppose: ‘a’ → ‘dd’ ‘b’ → delete everything else → unchanged

Input: [a,c,d,b,b,c,a]

Output: [d,d,c,d,c,d,d]

A naive approach repeatedly inserts and deletes elements. That’s dangerous. Why? Because insertion into the middle of an array shifts subsequent elements. Repeated shifting can lead to: O(n²)

The better solution uses two passes.

Pass 1: Determine Final Size

Scan forward. During this pass:

remove b
retain other characters
count occurrences of a

At the end, we know the final required size.

Pass 2: Write Backward

Now process from the end. If the character is: a

write: dd

Otherwise, copy the character. Why backward? Because the output is larger than the input. Writing from the back prevents us from overwriting characters that have not yet been processed. This gives us the general pattern: Forward pass ↓ Understand / count ↓ Determine final size ↓ Backward pass ↓ Construct result

This pattern is extremely reusable in:

URL encoding
escaping
XML/JSON transformations
character normalization
replacing spaces
in-place array transformations
merging arrays from the back

12. Palindrome: The Two-Pointer Pattern

A palindrome reads the same forward and backward. But the problem here has an important definition:

Ignore non-alphanumeric characters.
Ignore case.

Therefore: “A man, a plan, a canal, Panama.”

is a palindrome. The obvious solution is to create a cleaned string and reverse it. But that requires additional memory. The better interview pattern is: left → ← right

At every step:

Skip non-alphanumeric characters from the left.
Skip non-alphanumeric characters from the right.
Compare.
Move both pointers inward.

Python: def is_palindrome(s): i = 0 j = len(s) - 1

while i < j:

while i < j and not s[i].isalnum(): i += 1

while i < j and not s[j].isalnum(): j -= 1

if s[i].lower() != s[j].lower(): return False

i += 1 j -= 1

return True

Complexity: Time: O(n) Space: O(1)

The key transformation is: Palindrome ↓ Compare symmetric characters ↓ Two pointers

That’s the pattern you want to remember.

13. Reverse Words: Global Transformation + Local Correction

Given: “Alice likes Bob”

produce: “Bob likes Alice”

The elegant technique is:

Step 1

Reverse the entire string: Alice likes Bob ↓ boB sekil ecilA

Step 2

Reverse every individual word: Bob likes Alice

So the pattern becomes: Global transformation ↓ Local correction ↓ Desired result

Python strings are immutable, so use a character array: def reverse_words(s): chars = list(s)

chars.reverse()

def reverse_range(left, right): while left < right: chars[left], chars[right] = chars[right], chars[left] left += 1 right -= 1

start = 0

while start < len(chars): end = start

while end < len(chars) and chars[end] != ’ ’: end += 1

reverse_range(start, end - 1) start = end + 1

return ‘’.join(chars)

Complexity in Python: Time: O(n) Space: O(n)

A mutable array implementation in another language could achieve O(1) auxiliary space; Python’s immutable str requires the character-list conversion.

14. Phone Mnemonics: Recognizing Backtracking

Consider the phone mapping: 2 → ABC 3 → DEF 4 → GHI 5 → JKL 6 → MNO 7 → PQRS 8 → TUV 9 → WXYZ

For: 227

we need combinations such as: AAP AAQ AAR AAS ABP …

The important observation is that each input digit creates a set of choices. That forms a tree: “” / | \ A B C /|\ /|\ /|\ D E F D E F D E F

This is a classic backtracking problem. The general structure is: choose ↓ recurse ↓ undo / overwrite

Python: MAPPING = { ‘0’: ‘’, ‘1’: ‘’, ‘2’: ‘ABC’, ‘3’: ‘DEF’, ‘4’: ‘GHI’, ‘5’: ‘JKL’, ‘6’: ‘MNO’, ‘7’: ‘PQRS’, ‘8’: ‘TUV’, ‘9’: ‘WXYZ’ }

def phone_mnemonics(phone): result = [] current = [‘’] * len(phone)

def backtrack(i): if i == len(phone): result.append(‘’.join(current)) return

for c in MAPPING[phone[i]]: current[i] = c backtrack(i + 1)

backtrack(0) return result

Complexity is output-sensitive. With at most four choices per digit: Recursive combinations: O(4ⁿ)

But if we actually return every string, the output itself contains n characters per result: O(n × 4ⁿ)

That’s an important Staff-level distinction:

Algorithmic complexity and output-generation cost are not always the same thing.

15. Look-and-Say: Run Scanning

The sequence begins: 1 11 21 1211 111221 312211 …

Each term describes the previous term. For: 111221

we say: three 1s two 2s one 1

giving: 312211

The important pattern is run scanning. Start ↓ Scan equal characters ↓ Count run ↓ Emit result ↓ Continue

Python: def next_term(s): result = [] i = 0

while i < len(s): j = i

while j < len(s) and s[j] == s[i]: j += 1

count = j - i

result.append(str(count)) result.append(s[i])

i = j

return ‘’.join(result)

Then: def look_and_say(n): s = “1”

for _ in range(n - 1): s = next_term(s)

return s

The important connection is that the same run-scanning pattern appears again in Run-Length Encoding. So don’t memorize those as separate techniques.

16. Roman Numerals: Think Right-to-Left

Roman numerals normally behave additively, except for subtractive combinations: IV IX XL XC CD CM

For example: MCMIV

A very elegant approach is to scan from right to left. Maintain: previous_value

If: current < previous

subtract. Otherwise: add.

Python: def roman_to_integer(s): values = { ‘I’: 1, ‘V’: 5, ‘X’: 10, ‘L’: 50, ‘C’: 100, ‘D’: 500, ‘M’: 1000 }

result = 0 previous = 0

for c in reversed(s): value = values[c]

if value < previous: result -= value else: result += value

previous = value

return result

Complexity: Time: O(n) Space: O(1)

Interview lesson

Sometimes the direction in which you scan the data can dramatically simplify the algorithm.

If the meaning of the current element depends on what comes after it, consider scanning from the right.

17. Valid IP Addresses: Don’t Over-Optimize a Tiny Search Space

Given: “19216811”

we need to generate valid IPv4 addresses. Each address contains exactly: 4 parts

Therefore we need exactly: 3 split points

Each part can contain at most three digits. So the number of possible configurations is bounded by: 3³ = 27

That’s tiny. Therefore, brute-force enumeration is completely reasonable. This is an important interview lesson:

Don’t optimize a search space that is already small.

Python: def valid_part(part): if not part: return False

if len(part) > 1 and part[0] == ‘0’: return False

return int(part) <= 255

def valid_ip_addresses(s): result = [] n = len(s)

for i in range(1, min(4, n)): p1 = s[:i]

if not valid_part(p1): continue

for j in range(i + 1, min(i + 4, n)): p2 = s[i:j]

if not valid_part(p2): continue

for k in range(j + 1, min(j + 4, n)): p3 = s[j:k] p4 = s[k:]

if valid_part(p3) and valid_part(p4): result.append( ‘.’.join([p1, p2, p3, p4]) )

return result

The lesson is broader than IP addresses: Count possibilities ↓ If tiny ↓ Enumerate ↓ Validate ↓ Prune

Don’t invent dynamic programming when enumeration is already sufficient.

18. Sinusoidal Strings: Look for Periodicity

Consider arranging: Hello_World!

in a three-row sinusoidal pattern. The tempting approach is to construct a two-dimensional matrix. But you don’t need one. The positions repeat periodically. The relevant index groups are: Row 1: 1, 5, 9, …

Row 2: 0, 2, 4, 6, …

Row 3: 3, 7, 11, …

The pattern repeats every: 4 characters

So we can exploit the periodicity directly: def snake_string(s): return ( s[1::4] + s[0::2] + s[3::4] )

Complexity: Time: O(n)

The deeper interview lesson:

Before building a complicated structure, ask whether the underlying index pattern is periodic.

This idea can appear in:

cyclic arrays
matrix traversal
serialization
scheduling
repeated patterns

19. Run-Length Encoding

Run-Length Encoding, or RLE, is another run-scanning problem. Input: aaaabcccaa

Output: 4a1b3c2a

Decoding: 3e4f2e

produces: eeeffffee

The encoding algorithm is straightforward: def encode(s): result = [] count = 1

for i in range(1, len(s) + 1): if i == len(s) or s[i] != s[i - 1]: result.append(str(count)) result.append(s[i - 1]) count = 1 else: count += 1

return ‘’.join(result)

Decoding: def decode(s): result = [] count = 0

for c in s: if c.isdigit(): count = count * 10 + int(c) else: result.append(c * count) count = 0

return ‘’.join(result)

Notice something interesting: count = count * 10 + digit

Again! The same recurrence appeared in:

String → Integer
Base Conversion
RLE decoding

This is one of the most valuable connections in the entire Part.

20. A Staff-Level RLE Observation: Output Can Explode

Suppose the input contains: 1000000a

The input is tiny. But the decoded output contains: 1,000,000 characters

Therefore we must distinguish: Input-processing complexity

from: Output-generation cost

This distinction matters in production systems. Imagine decompressing: 1 KB

into: 1 GB

The algorithm may technically be linear in the input, but the system still has to allocate, transmit, or process the enormous output. That is the kind of follow-up that differentiates a Staff-level answer from a purely algorithmic one.

21. Rabin–Karp: The Advanced Problem

The final problem is substring search. Given: text = “hello world” pattern = “world”

return: 6

The brute-force approach compares the pattern against every possible position. Worst case: O(nm)

where:

n = text length
m = pattern length

The problem is repeated character comparisons. Rabin–Karp attacks this repetition using a rolling hash.

22. The Core Idea Behind Rabin–Karp

Instead of immediately comparing: pattern

against: window

character by character, compute a numerical fingerprint for each. If: hash(window) != hash(pattern)

then the strings definitely differ. So we can skip the expensive comparison. If: hash(window) == hash(pattern)

we still need to compare the actual strings. Why? Because: hash(A) == hash(B)

does not guarantee: A == B

Hash collisions are possible. That is a critical detail.

23. Rolling Hash

Suppose a window contains: ABC

and: A = 0 B = 1 C = 2 BASE = 10

Then: hash = 0 × 100 + 1 × 10 + 2 = 12

Now slide: ABC → BCD

We don’t want to recalculate the entire hash. Instead:

Step 1

Remove the outgoing character.

Step 2

Shift the remaining value.

Step 3

Add the incoming character. The formula becomes: new_hash = (old_hash - old_char × BASE^(m-1)) × BASE + new_char

This is the core idea behind rolling hashes.

24. Python Implementation

def rabin_karp(pattern, text): m = len(pattern) n = len(text)

if m > n: return -1

BASE = 256

pattern_hash = 0 window_hash = 0 power = 1

for i in range(m): pattern_hash = pattern_hash * BASE + ord(pattern[i]) window_hash = window_hash * BASE + ord(text[i])

if i < m - 1: power *= BASE

for i in range(n - m + 1):

if window_hash == pattern_hash: if text[i:i + m] == pattern: return i

if i < n - m: window_hash = ( (window_hash - ord(text[i]) * power) * BASE + ord(text[i + m]) )

return -1

Expected complexity with a good hash: O(n + m)

But the nuanced interview answer is: Average / Expected: O(n + m) Worst case: O(nm)

because excessive hash collisions can force repeated explicit comparisons.

25. Rabin–Karp vs KMP vs Boyer–Moore

You don’t necessarily need to implement every string-search algorithm in an interview. But you should understand their high-level ideas:

Algorithm	Core Idea
Brute Force	Compare at every position
Rabin–Karp	Rolling hash
KMP	Prefix/failure function
Boyer–Moore	Skip using mismatch information

The important Staff-level skill is knowing why you would choose one over another, rather than simply knowing their names.

26. The 10 Patterns You Should Actually Remember

Now compress the entire Part into reusable patterns.

Pattern 1 — Two Pointers

Used in: Palindrome

Think: left → ← right

Compare symmetric elements.

Pattern 2 — Forward + Backward Pass

Used in: Replace and Remove Reverse Words

Think: Pass 1 Understand / count / locate ↓ Pass 2 Construct final result

Especially useful when output size changes.

Pattern 3 — Build a Number

Core recurrence: value = value * base + digit

Used in: String → Integer Base Conversion RLE decoding

Pattern 4 — Extract Digits

digit = value % base value //= base

Used when converting numbers into another representation.

Pattern 5 — Reverse + Local Correction

Reverse everything ↓ Reverse individual components

Used in: Reverse Words

Pattern 6 — Backtracking

choose ↓ recurse ↓ restore

Used in: Phone Mnemonics

And later:

subsets
permutations
combinations
N-Queens
Sudoku
word search

Pattern 7 — Run Scanning

Scan equal characters ↓ Count ↓ Emit

Used in: Look-and-Say Run-Length Encoding

Pattern 8 — Small Search-Space Enumeration

Generate candidates ↓ Validate ↓ Prune

Used in: Valid IP Addresses

Pattern 9 — Right-to-Left Parsing

current < previous ↓ subtract

current >= previous ↓ add

Used in: Roman Numerals

Pattern 10 — Rolling Hash

Remove outgoing ↓ Shift ↓ Add incoming

Used in: Rabin–Karp

These ten patterns are much more valuable than memorizing thirteen independent solutions.

27. Complexity Cheat Sheet

Problem	Time	Extra Space
Integer → String	O(n)	O(n)
String → Integer	O(n)	O(1)
Base Conversion	O(n + output)	O(output)
Spreadsheet Column	O(n)	O(1)
Replace / Remove	O(n)	O(1)*
Palindrome	O(n)	O(1)
Reverse Words	O(n)	O(1)*
Phone Mnemonics	O(4ⁿ × n), output-sensitive	O(n) recursion
Look-and-Say	Output-dependent	Output-dependent
Roman → Integer	O(n)	O(1)
IP Addresses	O(1)**	O(1)**
Sinusoidal	O(n)	O(n) output
RLE	O(n)	O(n) output
Rabin–Karp	Expected O(n + m)	O(1)

Assumes mutable array/bytearray representation. ** IPv4 has a fixed four-part structure; output storage is excluded. The key Staff-level habit is not merely saying:

“It’s O(n).”

Instead, explain what is being processed, what memory is required, and whether the output itself dominates the cost.

28. The Six Problems I Would Prioritize

If you’re preparing for serious coding interviews, prioritize these first.

Tier 1 — Must Code From Memory

1. String ↔ Integer Memorize conceptually: result = result * base + digit

2. Replace and Remove Understand: forward pass + backward pass

3. Palindrome Understand: left + right

4. Reverse Words Understand: reverse whole + reverse each word

5. Phone Mnemonics Understand: backtracking

6. Rabin–Karp Understand: rolling hash

Then move to:

base conversion
spreadsheet encoding
IP enumeration
Roman numerals
RLE
look-and-say

This ordering gives you maximum pattern coverage rather than maximum problem count.

29. What You Should NOT Memorize

Don’t memorize code line by line. Memorize the mental templates.

String → Integer

result = result × base + digit

Integer → String

digit = x % base x //= base reverse

Palindrome

left right skip compare

Replace / Remove

count final size write backward

Reverse Words

reverse all reverse each word

Phone Mnemonics

position → choices → recurse

RLE

scan run → count → emit

Rabin–Karp

hash window → remove outgoing → shift → add incoming

That is the knowledge you actually need under interview pressure.

30. A Critical Python Interview Question: “Do It In-Place”

Suppose an interviewer asks:

“Can you modify the string in-place?”

Don’t blindly start coding. Say:

“Python str is immutable. If true in-place mutation is required, I’ll represent it as a list of characters or a bytearray.”

For example: chars = list(s)

chars[i] = ‘x’

result = ‘’.join(chars)

This demonstrates something beyond algorithm knowledge: language-specific engineering judgment.

31. Part 5 → Part 6: Arrays Become Characters

This is one of the most important connections in the series. Part 5 introduced ideas such as: Arrays ↓ Two pointers ↓ Partition ↓ In-place manipulation

Part 6 applies the same thinking to strings: Strings ↓ Characters are array elements ↓ Two pointers ↓ In-place transformation

For example:

Part 5

Delete duplicates: read pointer + write pointer

Part 6

Palindrome: left pointer + right pointer

Similarly:

Part 5

Reverse matrix layer.

Part 6

Reverse the complete string and then individual words. So Part 6 is not really a completely new topic. It is:

Array thinking applied to character sequences.

32. Part 6 → Advanced Algorithms

Part 6 also prepares you for later algorithmic topics.

String Parsing

Problems such as: 6.1 6.2 6.3 6.9

prepare you for:

lexing
parsing
serialization

Backtracking

Phone mnemonics prepares you for:

subsets
permutations
constraint search

Hashing

Rabin–Karp prepares you for:

hash tables
rolling hashes
deduplication
distributed hashing

Run Scanning

Look-and-say and RLE prepare you for:

compression
stream processing
log processing

This is why studying patterns is more powerful than studying isolated problems.

33. The Staff-Level Perspective

At a Staff-level interview, don’t stop after saying:

“Time complexity is O(n).”

Go one level deeper. Ask:

1. Representation

Is the string immutable? Python str → immutable

2. Memory

Can we avoid allocating another string?

3. Output Size

Could the output be much larger than the input? For example: Phone mnemonics → exponential output RLE decoding → potentially enormous output

4. Collision Behavior

For Rabin–Karp: Equal hashes ≠ equal strings

5. Input Assumptions

For Roman numerals: Is the input guaranteed valid?

For IP addresses: The search space is bounded.

6. Production Implications

Ask:

“What changes when the input is huge?”

For substring search: Would I still use Rabin–Karp?

For compression: What happens if 1 KB expands to 1 GB?

Those questions demonstrate engineering judgment beyond textbook algorithm knowledge.

34. A Framework for Any New String Problem

When you see a new string problem, mentally run this decision process: STRING PROBLEM │ ▼ Is the string immutable? │ ┌─────┴─────┐ ▼ ▼ YES NO │ ▼ Need character mutation? │ ┌────┴────┐ ▼ ▼ YES NO │ │ ▼ ▼ list/bytearray str │ ▼ Two pointers? │ ┌───┴────┐ ▼ ▼ left/right read/write │ │ ▼ ▼ palindrome transform │ ▼ Conversion? │ ▼ result = result * base + digit │ ▼ Enumeration? │ ▼ backtracking │ ▼ Substring search? │ ▼ rolling hash / KMP

This is the kind of mental model you want during an interview.

35. The Final Mental Model

If you remember only ten things from Part 6, remember these: 1. Two pointers left, right

2. Read/write pointers read, write

3. Build a number value = value * base + digit

4. Extract a digit digit = value % base value //= base

5. Reverse reverse whole + reverse components

6. Run scanning while same: count++

7. Backtracking choose recurse restore

8. Bounded enumeration generate validate prune

9. Right-to-left parsing current vs previous

10. Rolling hash remove shift add

Final Takeaway

Part 6 is not really about strings. It is about recognizing transformations. A string problem might secretly be: Two pointers

or: In-place transformation

or: Digit accumulation

or: Reverse + local correction

or: Backtracking

or: Run scanning

or: Bounded enumeration

or: Rolling hash

That is the real progression: String ↓ Representation ↓ Pattern ↓ Invariant ↓ Algorithm ↓ Complexity ↓ Trade-offs

For Staff/Principal interviews, this shift is crucial. Don’t ask:

“Which string problem is this?”

Ask:

“What transformation is hiding underneath this problem?”

If you can implement 6.1, 6.4, 6.5, 6.6, 6.7, 6.10, 6.12, and 6.13 from scratch, explain their invariants, derive their complexity, and discuss their trade-offs, you have extracted most of the interview value from Part 6.

Up Next: Part 7 — Linked Lists

Strings taught us to think about: representation + pointers + transformations + invariants

Part 7 takes pointer-based reasoning to the next level. We’ll move from: characters ↓ indices ↓ two pointers

to: nodes ↓ references ↓ pointer rewiring ↓ fast/slow pointers ↓ cycles ↓ list transformations

The algorithms become different. But the fundamental interview skill remains the same:

Recognize the pattern, establish the invariant, and eliminate unnecessary work.