Split a Chunked Text Stream into Line-Balanced Parts

A text file arrives through an iterator that yields arbitrary string chunks. Split its content into n ordered parts while keeping every line intact and making the numbers of lines in any two parts differ by at most one. Implement `split_balanced_lines(chunks: string[], parts: int) -> string[]`. The array is a portable fixture for the source iterator; chunk boundaries may occur in the middle of a line. ### Constraints & Assumptions The source does not state the unit of balance. This practice version balances **line counts**, not bytes: arbitrary line lengths can make a one-byte balance impossible while keeping lines intact. - `1 <= parts <= 10000`; at most 100000 chunks and 1000000 characters in total. Chunks may be empty. - A newline `\n` terminates a line and remains attached to that line. A final nonempty fragment without a newline is also a line. A final newline does not create an extra empty line after it. An empty file has zero lines. - Other characters, including `\r`, are ordinary content; do not normalize line endings. - Preserve exact content and line order. Every output part is a concatenation of consecutive whole lines. - For L lines, each part contains either `floor(L/parts)` or `ceil(L/parts)` lines, and the total is L. Any placement of the larger parts is valid; there is no required earliest-extra-lines policy. - Always return exactly parts strings; parts with zero lines are empty. ### Examples of Valid Outputs ```text chunks = ["a\nb", "\nc\n", "d"], parts = 3 one valid result = ["a\nb\n","c\n","d"] ``` ```text chunks = ["\n", "\n"], parts = 3 one valid result = ["\n","\n",""] ``` Explain time and memory complexity. For a real one-pass iterator with unknown total line count, discuss why exact final balance may require buffering/spooling or a preliminary counting pass; do not claim that already-emitted part boundaries can always be fixed with constant memory. ```hint Separate chunk boundaries from line boundaries A partial line can span several iterator yields. Determine the total line allocation independently of those arbitrary chunk sizes. ``` ### Clarifying Questions Does balance refer to line count or byte count? Must output order preserve the file? Can the iterator be rewound? Is total line count known in advance? ### What a Strong Answer Covers Correct line reconstruction across chunk boundaries, any balanced allocation, preservation of exact content, and a realistic account of buffering or multiple passes. ### Follow-up Questions How would you validate an alternative correct partition without comparing it to one preferred output? What extra capability is required for bounded-memory streaming when the line count is initially unknown?