Format messages with paginated suffixes
Company: TikTok
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a message string s and an integer width w. Split s into multiple chunks, preserving character order, and append a suffix "i/n" to each chunk where i is the 1-based index and n is the total number of chunks. Part 1: Assume the suffix does not count toward width; output all chunked strings with their suffixes. Part 2 (hard): The suffix must count toward width and n is unknown in advance because the suffix length depends on n. Design an algorithm to determine n and produce the chunks so that each chunk (content + a single space + "i/n") fits within w characters. Handle edge cases (e.g., when w is too small to fit even "1/1"), analyze time and space complexity, and justify correctness.
Quick Answer: This question evaluates string-processing and algorithm-design skills, including handling variable-length metadata, preserving character order, managing boundary cases, and formal time/space complexity reasoning.
Format Messages with Paginated Suffixes (Suffix Free of Width)
You are given a message string `s` and an integer width `w`. Split `s` into chunks of at most `w` characters, preserving character order, then append a suffix ` i/n` to each chunk, where `i` is the 1-based chunk index and `n` is the total number of chunks. Each returned line is `content + " " + "i/n"`.
In this part the suffix does NOT count toward the width budget `w` — i.e. you chunk `s` purely by `w` content characters and then tack the suffix on afterward.
Return the list of formatted lines.
Rules / edge cases:
- `n = ceil(len(s) / w)`; if `s` is empty, treat it as a single empty chunk so `n = 1` and the line is `" 1/1"`.
- If `w <= 0`, return an empty list (no valid chunking is possible).
Example: `s = "helloworld"`, `w = 5` → `["hello 1/2", "world 2/2"]`.
Constraints
- 0 <= len(s)
- w may be any integer; w <= 0 yields an empty result
- Characters are kept in their original order across chunks
- The suffix " i/n" is appended AFTER chunking and does not consume width
Examples
Input: ("abcdefgh", 3)
Expected Output: ['abc 1/3', 'def 2/3', 'gh 3/3']
Explanation: len 8, w 3 -> n = ceil(8/3) = 3 chunks 'abc','def','gh'; last chunk is short.
Input: ("helloworld", 5)
Expected Output: ['hello 1/2', 'world 2/2']
Explanation: len 10, w 5 -> exactly 2 full chunks.
Hints
- The number of chunks is fixed up front: n = ceil(len(s) / w). Because the suffix is free, w only governs the content slices.
- Slice s in fixed strides of w: chunk k is s[k*w : (k+1)*w]. The final chunk may be shorter than w.
- Handle the empty-string case separately so it still emits exactly one line, " 1/1".
Format Messages with Paginated Suffixes (Suffix Counts Toward Width)
Same setup as the previous part, but now the suffix ` i/n` MUST count toward the width: each emitted line `content + " " + "i/n"` must have total length at most `w`. The hard part is that `n` is unknown in advance — the suffix length depends on the number of digits in `n` (and `i`), which depends on `n` itself.
Design an algorithm that determines `n` and produces chunks so that every line fits within `w`.
Approach: search for the smallest feasible `n`. For a candidate `n` reserve a uniform worst-case suffix budget of `1 (space) + digits(n) + 1 (slash) + digits(n)` characters (the worst suffix is ` n/n`). The per-chunk content budget is then `content_width = w - reserved`. A candidate `n` works when `content_width >= 1` and `content_width * n >= len(s)`. Because increasing `n` never shrinks `reserved`, once `content_width < 1` the task is impossible.
Return the list of formatted lines, or an empty list if `w` is too small to fit even "1/1" plus any required content.
Edge cases:
- If `s` is empty, one line `" 1/1"` is emitted when `w >= 4`, else `[]`.
- When `w` is too small (e.g. `w = 3` with non-empty `s`), return `[]`.
Example: `s = "abcdefgh"`, `w = 10` → reserved for n=2 is `1+1+1+1 = 4`, content_width 6, two chunks → `["abcdef 1/2", "gh 2/2"]` (each length <= 10).
Constraints
- 0 <= len(s)
- Every emitted line content + " " + "i/n" must have length <= w
- n is not given; it must be derived so the suffix (whose length grows with digits(n)) still fits
- Return [] when no n can satisfy the width (e.g. w too small for "1/1" plus content)
Examples
Input: ("abcdefgh", 10)
Expected Output: ['abcdef 1/2', 'gh 2/2']
Explanation: n=1 reserves 4 -> content 6, 6*1=6 < 8 fails; n=2 reserves 4 -> content 6, 6*2=12 >= 8 works. Each line <= 10.
Input: ("hello", 7)
Expected Output: ['hel 1/2', 'lo 2/2']
Explanation: n=1: content 3, 3<5 fails; n=2: content 3, 3*2=6>=5 works -> chunks of 3 then 2. Lines 'hel 1/2' (7) and 'lo 2/2' (6).
Hints
- The suffix length is not fixed: it depends on digits(n). Reserve a uniform worst-case budget of 1 + digits(n) + 1 + digits(n) so the content boundary is the same for every chunk.
- For a candidate n, content_width = w - reserved. The candidate is feasible iff content_width >= 1 and content_width * n >= len(s). Search for the smallest such n.
- Monotonicity: raising n never decreases reserved, so once content_width drops below 1 the problem is impossible — return [] immediately.