Remove Extra Spaces from a String

Difficulty Level Easy
Frequently asked in Capgemini Infosys MAQ o9 solutions TCS
StringViews 2094

Problem Statement

In the “Remove Extra Spaces from a String” problem we have given a string “s”. Write a program to remove all extra_spaces from the given string.

Input Format

The first and only one line containing a string s with some spaces.

Output Format

Print a string after removing all the extra_spaces.

Constraints

  • 1<=|s|<=10^6
  • s[i] must be a lower case English alphabet, “,”, “.”, “?” or space ” “.

Example

tutorialcup        is the  best   platform.
tutorialcup is the best platform.

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 a non-space character, the character is copied to the location of the ‘i’ pointer and then, increment both i,j

4. if the character is either a full stop, question mark or a comma then remove any preceding space

5. If there are two consecutive spaces, remove one space by copying only one space to the i pointer

Implementation

C++ Program for Remove Extra Spaces from a String

#include <iostream>
using namespace std;

int main()
{
  string s;
  getline(cin, s);
  int n = s.length();
  int i = 0, j = -1;
  int flag=0;
  while(++j<n&&s[j]==' ');
  while(j<n)
  {
    if(s[j]!=' ')
    {
      if((s[j]=='.'||s[j]==','||s[j]=='?')&&i-1>=0&&s[i-1]==' ')
        s[i-1]=s[j++];
      else
        s[i++]=s[j++];
      flag=0;
    }
    else if(s[j++]==' ')
    {
      if(!flag)
      {
        s[i++]=' ';
        flag=1;
      }
    }
  }
  if(i<=1)
    s.erase(s.begin() + i, s.end());
  else
    s.erase(s.begin()+i-1,s.end());
  cout<<s;
  return 0;
}

Java Program for Remove Extra Spaces from a String

import java.util.Scanner;
class sum
{
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        String s = sr.nextLine();
  int n = s.length();
        char ans[] = new char[n];
  int i = 0, j = -1;
  int flag=0;
  while(++j<n&&s.charAt(j)==' ');
  while(j<n)
  {
    if(s.charAt(j)!=' ')
    {
      if((s.charAt(j)=='.'||s.charAt(j)==','||s.charAt(j)=='?')&&i-1>=0&&s.charAt(i-1)==' ')
        ans[i-1]=s.charAt(j++);
      else
        ans[i++]=s.charAt(j++);
      flag=0;
    }
    else if(s.charAt(j++)==' ')
    {
      if(flag==0)
      {
        ans[i++]=' ';
        flag=1;
      }
    }
  }
        System.out.println(ans);
    }
}

jvsuqs bwdbh, wdv  ud  .

jvsuqs bwdbh, wdv ud.

Complexity Analysis for Remove Extra Spaces from a String

Time Complexity

O(n) where n is the size of the given string “s”. Here we simply traverse the string and removed all extra_spaces here.

Space Complexity

O(1) because we don’t use any extra spaces here. Simply update the given string and finally print it after final updates.

Translate ยป