# Remove Multiple Spaces in String by Using Constant Memory

## Problem Description:

The problem here makes me think: Can we come up with a method to remove multiple spaces in a string in O(N) time and O(1) space where the string is stored as an array rather than a linked list? After I searched out the internet and I found it is impossible but there are still things worth doing on it. I basically have two things to discuss and you are very welcome to leave any comments on them.

## A. Multiple spaces could be moved into the tail in O(1) space

Although I say it is impossible to achieve our goal here to remove multiple spaces in string presented in an array. There is one thing we can do better than simple copying one character by one character from the original array to a second array from the beginning with space being examined. By saying we do not have to use the second array from the beginning, I mean two things: (1) we still need it at the end: take (N) spaces; (2) we can use the original array to store all the extra spaces we need to remove: before this, we achieved to use const memory (better than nothing).  Please see the following code:

## B. Double Linked List Surely is Our Best Choice

What if we can choose the data structure of the input string?  I would be silly if so and I still choose std::string or std::vector. I would surely choose Linked List to store the string, and more specifically, it should be doubly linked list. I implemented all the logic by making a singly list as the following code shows, one can see at the end or the related comment that Why I say doubly linked list is the best choice both here in this post and in my last post here at the end.

## Conclusions:

I think coding is quite fun and we can learn a lot from every small piece of code. For this particular problem here “Remove Multiple Spaces in String by Using Constant Memory”. I discussed two points: (1) Multiple spaces could be moved into the tail in O(1) space and (2) Double Linked List Surely is Our Best Choice.

A final little tip: I use default parameter here and make the gao() function more general so that it actually can remove not only multiple spaces but multiple characters you specify when you pass the parameter to the function.