Remove Extra Spaces from a string

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;
}
Try It

 


Next > < Prev
Scroll to Top