Given a string, write a function to remove all extra spaces from the given string
Example
INPUT
s = ” I Love Programming , ”
OUTPUT
“I Love Programming, ”
Time Complexity : O(n)
Space Complexity : O(1)
Algorithm
1. Traverse the string with two pointers i,j both pointing to the starting of the string
2. ‘i’ pointer keeps track of next position to be filled in output string and ‘j’ pointer is to read all characters one by one
3. If the character is non-space character, the character is copied to the location of the ‘i’ pointer and then, increament both i,j
4. if the charceter is either fullstop, questionmark or a comma then remove any preceeding space
5. If there are two consecutive spaces, remove one space by copying only one space to the i pointer
C++ Program
#include <bits/stdc++.h>
using namespace std;
void removeExtraSpaces(string &s)
{
// n is length of the original string
int n = s.length();
//pointer i to keep trackof next position and j to traverse
int i = 0, j = -1;
// flag that sets to true is space is found
bool spaceFound = false;
// Handles leading spaces
while (++j < n && s[j] == ' ');
// read all characters of original string
while (j < n)
{
// if current characters is non-space
if (s[j] != ' ')
{
//if any preceeding space before ,.and ?
if ((s[j] == '.' || s[j] == ',' ||
s[j] == '?') && i - 1 >= 0 &&
s[i - 1] == ' ')
s[i - 1] = s[j++];
else
// copy current character to index i
// and increment both i and j
s[i++] = s[j++];
// set space flag to false when any
// non-space character is found
spaceFound = false;
}
// if current character is a space
else if (s[j++] == ' ')
{
// If space is seen first time after a word
if (!spaceFound)
{
s[i++] = ' ';
spaceFound = true;
}
}
}
// Remove trailing spaces
if (i <= 1)
s.erase(s.begin() + i, s.end());
else
s.erase(s.begin() + i - 1, s.end());
}
int main()
{
string s =" I Love Programming ";
removeExtraSpaces(s);
cout << s<<endl;
return 0;
}
