Format messages with paginated suffixes
Overview
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.
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.