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