Um das wiederholte Backtracking auszuschließen und Komplexität auf O(N) zu begrenzen brauchst Du das .* am Anfang nicht. Da genügt das \S vor dem \s+. Das stellt sicher, dass die Regex nicht bei jedem Whitespace mit dem Suchen anfangen muss, sondern nur bei Whitespace, direkt hinter einem non-Whitespace.

Ich habe \S dann noch in eine Look-behind Assertion gepackt, damit das Zeichen vor dem Whitespace nicht vom s/// mit ersetzt wird.