Your regular expression [^a-zA-Z0-9]\s/g says match any character that is not a number or letter followed by a space.
Remove the \s and you should get what you are after if you want a _ for every special character.
var newString = str.replace(/[^A-Z0-9]/ig, "_");
That will result in hello_world___hello_universe
If you want it to be single underscores use a + to match multiple
var newString = str.replace(/[^A-Z0-9]+/ig, "_");
That will result in hello_world_hello_universe