Difference between nodes of alternate vertical levels in a tree
May 19, 2018
Find numbers with more than k-bits in their binary representations
May 28, 2018

Remove all white spaces from a string

Given a string that may have white spaces, write code to remove all white spaces from than string. For example:

Input String: "IT IS HOT OUTSIDE"
Output String: "ITISHOTOUTSIDE"
Input String: "   I  T I  S    HOT   "
Output String: "ITISHOT"

Solution:
The brute-force way of solving it is to shift all the elements when a white-space is encountered.

// HELPER FUNCTION TO CHECK IF A CHARACTER IS WHITE SPACE
bool isWhiteSpace(char ch)
{
  return (ch == ' ' || ch == '\t' || ch == '\n' || ch == '\r');
}
void removeWhiteSpace(char* str)
{
  int i=0;
  while(str[i] != '\0')
  {
    if(isWhiteSpace(str[i]))
    {
      for(int j=i; str[j] != '\0'; j++)
      {
        str[j] = str[j+1];
      }
    }
    else
      i++;
  }
  str[i] = '\0';
}

In this solution, we are shifting all the characters for each white space encountered. The shifting takes O(k) time, where k is the number of characters on the right side.
The worst case time taken by above solution is O(n2). We can bring down the time taken, to linear time, if we follow the sliding window of variable length as discussed below:
Solution-2 (Sliding Window approach):
We take two variables i and j holding the index of starting index and end index of the window, that we are operating on.
Initially, i is set to the first whitespace found from the start of the string and j is set to position (i+1).

Move j forward, and whenever, j points to a non-white character, move that character to position str[i] and increment i. So, at any point of time, i holds the index where the current non-white character should go, and j holds the index of the current element. This will move all the non-white-space characters of the string toward the left. Have a look at the code below

// HELPER FUNCTION TO CHECK IF A CHARACTER IS WHITE SPACE
bool isWhiteSpace(char ch)
{
  return (ch == ' ' || ch == '\t' || ch == '\n' || ch == '\r');
}
void removeWhiteSpace(char* str)
{
  int i=0; int j=0;
  // PRE-PROCESSING
  while(str[i] != '\0' && !isWhiteSpace(str[i]))
    i++;
  if(str[i] == '\0'){ return; }
  j = i+1;
  // MAIN LOGIC
  while(str[j] != '\0')
  {
    if(isWhiteSpace(str[j]))
      j++;
    else
    {
      str[i] = str[j];
      i++; j++;
    }
  }
  str[i] = '\0';
}

Please note that last statement in the function. This is required because the length of the string is reduced, so the string terminator should also move forward.
In this code, we are traversing the string only once. It is a linear-time solution, that takes constant extra space. It is a very simple example, of a reasonably powerful concept called, Sliding Window.

Leave a Reply

Your email address will not be published. Required fields are marked *