Given a character array which contains some spaces. we have to replace all the spaces with the string '%20'. This algorithm is commonly used during HTML encoding of the URLs in the web browsers. Assume that the array has enough space at the end to accommodate the expanded string, how do we do this efficiently?
The following solution uses no extra space and runs in O(n) time. The trick here is to start copying the characters from the end, and wherever we find space replace it with '%20'. The following C++ code does exactly that.