String Algorithms

String Processing & Parsing

Build, parse and transform strings character by character: encodings, digit arithmetic and conversions.

Easy, about 60 minutes to practise.

1Understand

The idea

Walk the string once, keeping just enough state for the task: the current number being read, the current run, a stack of what is open. Build the result in a list and join it at the end. For digit-by-digit arithmetic, process from the least significant end and carry over.

Intuition

Walk the string once, keeping just enough state for the task: the current number being parsed, the current run length, a stack of open frames. Build the output in a list and join at the end.

Digit-by-digit arithmetic processes from the least significant end with a carry. Parsing problems fail on edge cases (signs, leading zeros, overflow) more often than on the main loop.

If nesting appears, you almost certainly want a stack alongside the scan.

What you will be able to do

  • Walk a string with an explicit index
  • Carry digits right to left
  • Design an unambiguous encoding

When to use it

  • Convert between a string and another representation
  • Numbers too large for built-in types, given as strings
  • Encode a list so it can be decoded exactly

2See it

Walkthrough

Parse with two indices

s = "42", accumulate digits into an integer.

1 / 5

i
4
2
01
i → index 0

num = 0. Read sign/spaces first in fuller parsers; here plain digits.

num = 0

Live template

Line 1 active

1i, out = 0, []
2while i < len(s):
3 token, i = read_token(s, i)
4 out.append(transform(token))
5return "".join(out)

Complexity: time O(n), space O(n)

One pass O(n + m) time and space for the output. Regex-heavy parsing can be clearer but harder to control edge cases in interviews. Prefer explicit index walks for digit/run problems.

Read the walkthrough as text

Add strings. num1 = "456", num2 = "77".

  1. i, j at last indices; carry = 0; out = [].
  2. Add 6+7+0 = 13 → write 3, carry 1.
  3. Add 5+7+1 = 13 → write 3, carry 1.
  4. Add 4+0+1 = 5 → write 5. Join reversed → "533".

In code:

  • while i >= 0 or j >= 0 or carry:
  • s = carry
  • if i >= 0: s += int(num1[i]); i -= 1
  • if j >= 0: s += int(num2[j]); j -= 1
  • out.append(str(s % 10)); carry = s // 10
  • return ''.join(reversed(out))

3Recognise it

Kinds of problems (8)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Encode / decode with length prefixes

    Example. Serialize list of strings with unambiguous delimiter.

    How. Store len#str per piece so payload may contain any char.

  • Arithmetic on digit strings (add, multiply)

    Example. Add two non-negative integers given as strings.

    How. Reverse or index from right; digit sums with carry.

  • Parse and convert (Roman numerals, string to integer)

    Example. Convert Roman numeral to integer.

    How. Scan left to right; subtract value if next symbol is larger.

  • Run-length compression

    Example. Compress consecutive repeats (count + char).

    How. Walk and group runs; emit len+char when run ends.

  • Character-to-word bijection (isomorphic strings, word pattern)

    Example. s and t isomorphic; pattern matches words.

    How. Two dicts map char→word and word→char; reject on conflict.

  • Common prefix of several strings

    Example. Longest common prefix in string list.

    How. Vertical scan until mismatch on column i across all strings.

  • Simulate writing in a pattern (zigzag)

    Example. Zigzag conversion on rows.

    How. Track row and direction; append char to row buckets then join.

  • Line layout (word wrap, text justification)

    Example. Format text to width w with justified lines.

    How. Greedy pack words per line; pad spaces evenly except last line rules.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Delimiter collision

    Why it happens. Comma or pipe separators are quick to implement.

    How it fails. Encode ["a,b","c"] with comma delimiter, decode splits payload wrong.

    Fix. Length-prefix encoding: `f"{len(str)}#{str}"`.

  • Carry lost

    Why it happens. Loop stops when one string ends.

    How it fails. Add "99" + "1" left-to-right without final carry, answer "90" instead of "100".

    Fix. Process from right; after loop if carry: append carry.

  • Sign or leading zeros

    Why it happens. Leading zeros look harmless in intermediate strings.

    How it fails. Parse "00123" as 123 but reject "0" or mishandle "-0" per spec.

    Fix. Strip sign first; handle all-zero -> single "0"; rebuild without leading zeros except zero.

  • One-way mapping

    Why it happens. One dict from s→t feels enough for isomorphism.

    How it fails. s="ab", t="cc": map a→c, b→c, t-side conflict not detected.

    Fix. Maintain maps in both directions (or check t→s on each assign).

  • Line rules mixed up

    Why it happens. Justify every line the same way.

    How it fails. Last line fully justified per middle-line rule, extra spaces where spec says left-align.

    Fix. Branch: last line and single-word lines have different spacing rules.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons