Format messages with paginated suffixes

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.

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

Hints

1. The number of chunks is fixed up front: n = ceil(len(s) / w). Because the suffix is free, w only governs the content slices.
2. Slice s in fixed strides of w: chunk k is s[k*w : (k+1)*w]. The final chunk may be shorter than w.
3. 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)

Hints

1. 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.
2. 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.
3. Monotonicity: raising n never decreases reserved, so once content_width drops below 1 the problem is impossible — return [] immediately.