674. Squeezing Out the Extra Spaces

A line of text is given. Print it with exactly ONE space between words and no space at the start or the end. The words themselves are unchanged and stay in their original order.

the sky is blue -> the sky is blue hello world -> hello world x -> x

## Read and write at different speeds

The reader skips runs of spaces and then copies a whole word. The writer emits a single space before each word EXCEPT the first, which is what removes the leading space and prevents a trailing one.

i = 0 while i < n: skip spaces if nothing left: stop j = i; advance j past the word if something has already been written: emit one space emit s[i .. j-1] i = j

## Why "space before each word except the first" is the right rule

The alternative, emitting a space AFTER each word and trimming the last one, also works and needs a trim. Putting the separator before the word makes the trailing case impossible rather than fixing it afterwards.

That choice is the same one that makes joining a list with a separator cleaner than appending and truncating, and it is worth preferring by default.

## The relationship with problem 621

621 reverses the word order and faces exactly these four space problems: leading, trailing, doubled, and the join. This keeps the order and isolates the spacing, so the two make a natural pair: solve this one first and 621 becomes only a direction change.

## Reading the input

The line contains spaces, so it must be read WHOLE. A whitespace-splitting reader sees the words already separated and makes the problem vanish, which is a good reason to be suspicious when a problem about spacing looks trivial.

## Boundaries

A single word comes back unchanged. The constraints promise at least one non-space character, so the output is never empty.

## Cost

Time O(n). Space O(n) for the output.

Constraints - `1 ≤ length of the line ≤ 200000` - the line contains at least one non-space character - characters are printable ASCII