JuniorCodeCommonNot answered yet
Collapse runs of spaces to a single space in place
Collapse every run of consecutive spaces in a mutable string to a single space. Do not trim leading or trailing spaces — only collapse runs (so "some string " becomes "some string ").
Requirements:
- O(n) time, O(1) extra space — edit in place and truncate.
void normalizeSpaces(std::string& s) {
// your code here
}Write the implementation.
Use a read and a write index. Copy each character to the write position, but write a space only when the previously written character was not a space. After the pass, resize the string to the write index. One pass, O(n) time, O(1) extra space; leading and trailing single spaces are preserved.
- ✗Trimming leading or trailing spaces when the spec says only collapse runs
- ✗Forgetting to resize the string, leaving stale characters at the tail
- ✗Calling
eraseper extra space, turning an O(n) job into O(n²)
- →How does the single trailing space survive when the input ends with several?
- →What changes if you also had to trim the ends?
Contents
Task
Collapse runs of spaces to a single space in place in O(n) time and O(1) space, without trimming the ends.
Solution
void normalizeSpaces(std::string& s) {
size_t write = 0;
for (size_t read = 0; read < s.size(); ++read) {
bool isSpace = s[read] == ' ';
bool prevSpace = write > 0 && s[write - 1] == ' ';
if (isSpace && prevSpace) continue; // skip the extra space
s[write++] = s[read];
}
s.resize(write); // truncate the tail
}Key points
- A space is written only when the previously written character is not a space.
- The ends are not trimmed: a single leading/trailing space survives.
resize(write)drops the leftover tail; all done in one O(n) pass.
Contents
