Given a string containing many consecutive spaces, trim all spaces so that all words should contain only a single space between them. The conversion should be done in-place and solution should handle trailing and leading spaces and also remove preceding spaces before common punctuation like full stop, comma and a question mark.
Examples:
Input:
str = " Hello Geeks . Welcome to neveropen . ";
Output:
"Hello Geeks. Welcome to neveropen."
Input:
str = "neveropen";
Output:
"neveropen"
(No change is needed)
This problem is an extension of Remove spaces from a given string
Method 1:
- The idea is to maintain 2 pointers. Initially both point to the beginning of the array.
- The first pointer keeps track of next position to be filled in output string.
- The second pointer is advanced to read all characters of the string one by one.
- On finding any non-space character, the character is copied to the location of the first pointer and then both the first and second pointers are advanced.
- If non-space character is a full stop, comma or a question mark, we also remove any preceding space before it.
- On finding consecutive space characters, one only space is copied to the location of the first pointer and rest are ignored. The leading and trailing spaces are handled separately in the solution.
Below is C++ implementation of above idea.
C++
// C++ program to implement custom trim() function#include <iostream>using namespace std;// Function to in-place trim all spaces in the// string such that all words should contain only// a single space between them.void removeSpaces(string &str){ // n is length of the original string int n = str.length(); // i points to next position to be filled in // output string/ j points to next character // in the original string int i = 0, j = -1; // flag that sets to true is space is found bool spaceFound = false; // Handles leading spaces while (++j < n && str[j] == ' '); // read all characters of original string while (j < n) { // if current characters is non-space if (str[j] != ' ') { // remove preceding spaces before dot, // comma & question mark if ((str[j] == '.' || str[j] == ',' || str[j] == '?') && i - 1 >= 0 && str[i - 1] == ' ') str[i - 1] = str[j++]; else // copy current character at index i // and increment both i and j str[i++] = str[j++]; // set space flag to false when any // non-space character is found spaceFound = false; } // if current character is a space else if (str[j++] == ' ') { // If space is encountered for the first // time after a word, put one space in the // output and set space flag to true if (!spaceFound) { str[i++] = ' '; spaceFound = true; } } } // Remove trailing spaces if (i <= 1) str.erase(str.begin() + i, str.end()); else str.erase(str.begin() + i - 1, str.end());}// Driver Codeint main(){ string str = " Hello Geeks . Welcome to" " neveropen . "; removeSpaces(str); cout << str; return 0;} |
Java
class Main{ public static String removeSpaces(String s) { int n = s.length(); int i = 0, j = -1; boolean spaceFound = false; // Handles leading spaces while (j < n - 1 && s.charAt(j + 1) == ' ') { j++; } // read all characters of original string while (j < n) { // if current characters is non-space if (s.charAt(j) != ' ') { // remove preceding spaces before dot, // comma & question mark if ((s.charAt(j) == '.' || s.charAt(j) == ',' || s.charAt(j) == '?') && i - 1 >= 0 && s.charAt(i - 1) == ' ') { s = s.substring(0, i - 1) + s.charAt(j) + s.substring(i); j++; } else { // copy current character at index i // and increment both i and j s = s.substring(0, i) + s.charAt(j) + s.substring(i + 1); i++; j++; } // set space flag to false when any // non-space character is found spaceFound = false; } else if (s.charAt(j) == ' ') { // If space is encountered for the first // time after a word, put one space in the // output and set space flag to true if (!spaceFound) { s = s.substring(0, i) + ' ' + s.substring(i + 1); i++; spaceFound = true; } j++; } } // Remove trailing spaces if (i <= 1) { s = s.substring(0, i); } else { s = s.substring(0, i - 1); } return s;}// Driver codepublic static void main(String[] args) { String str = " Hello Geeks . Welcome to" + " neveropen . "; str = removeSpaces(str); System.out.println(str);} } |
Python3
# Python code for the above approachdef removeSpaces(s): # n is length of the original string n = len(s) # i points to next position to be filled in # output string/ j points to next character # in the original string i = 0 j = -1 # flag that sets to true is space is found spaceFound = False # Handles leading spaces while j < n - 1 and s[j + 1] == ' ': j += 1 # read all characters of original string while j < n: # if current characters is non-space if s[j] != ' ': # remove preceding spaces before dot, # comma & question mark if ((s[j] == '.' or s[j] == ',' or s[j] == '?') and i - 1 >= 0 and s[i - 1] == ' '): s = s[:i - 1] + s[j] + s[i:] j += 1 else: # copy current character at index i # and increment both i and j s = s[:i] + s[j] + s[i + 1:] i += 1 j += 1 # set space flag to false when any # non-space character is found spaceFound = False # if current character is a space elif s[j] == ' ': # If space is encountered for the first # time after a word, put one space in the # output and set space flag to true if not spaceFound: s = s[:i] + ' ' + s[i + 1:] i += 1 spaceFound = True j += 1 # Remove trailing spaces if i <= 1: s = s[:i] else: s = s[:i - 1] return s# Driver Codestr = " Hello Geeks . Welcome to" \ " neveropen . "str = removeSpaces(str)print(str)# This code is contributed by adityasharmadev01 |
C#
// C# program to implement custom trim() functionusing System;public class Gfg{ public static void Main() { string str = " Hello Geeks . Welcome to" + " neveropen . "; removeSpaces(ref str); Console.WriteLine(str); } // Function to in-place trim all spaces in the // string such that all words should contain only // a single space between them. public static void removeSpaces(ref string str) { // n is length of the original string int n = str.Length; // i points to next position to be filled in // output string/ j points to next character // in the original string int i = 0, j = -1; // flag that sets to true is space is found bool spaceFound = false; // Handles leading spaces while (++j < n && str[j] == ' '); // read all characters of original string while (j < n) { // if current characters is non-space if (str[j] != ' ') { // remove preceding spaces before dot, // comma & question mark if ((str[j] == '.' || str[j] == ',' || str[j] == '?') && i - 1 >= 0 && str[i - 1] == ' ') str = str.Remove(i - 1, 1).Insert(i - 1, str[j++].ToString()); else { // copy current character at index i // and increment both i and j str = str.Remove(i, 1).Insert(i, str[j++].ToString()); i++; } // set space flag to false when any // non-space character is found spaceFound = false; } // if current character is a space else if (str[j++] == ' ') { // If space is encountered for the first // time after a word, put one space in the // output and set space flag to true if (!spaceFound) { str = str.Remove(i, 0).Insert(i, " "); i++; spaceFound = true; } } } // Remove trailing spaces if (i <= 1) str = str.Remove(i, n - i); else str = str.Remove(i - 1, n - i + 1); }} |
Javascript
// JavaScript program to implement custom trim() function// Function to in-place trim all spaces in the// string such that all words should contain only// a single space between them.function removeSpaces(str) { // n is length of the original string let n = str.length; // i points to next position to be filled in // output string/ j points to next character // in the original string let i = 0, j = -1; // flag that sets to true is space is found let spaceFound = false; // Handles leading spaces while (++j < n && str[j] == ' '); // read all characters of original string while (j < n) { // if current characters is non-space if (str[j] != ' ') { // remove preceding spaces before dot, // comma & question mark if ((str[j] == '.' || str[j] == ',' || str[j] == '?') && i - 1 >= 0 && str[i - 1] == ' ') str = str.substr(0, i - 1) + str[j++] + str.substr(i); else // copy current character at index i // and increment both i and j str = str.substr(0, i++) + str[j++] + str.substr(i); // set space flag to false when any // non-space character is found spaceFound = false; } // if current character is a space else if (str[j++] == ' ') { // If space is encountered for the first // time after a word, put one space in the // output and set space flag to true if (!spaceFound) { str = str.substr(0, i++) + ' ' + str.substr(i); spaceFound = true; } } } // Remove trailing spaces if (i <= 1) str = str.substr(0, i); else str = str.substr(0, i - 1); return str;}// Driver Codelet str = " Hello Geeks . Welcome to"+ " neveropen . ";str = removeSpaces(str);console.log(str); |
Output:
Hello Geeks. Welcome to neveropen.
Time complexity of above solution is O(n).
Auxiliary Space is O(1) as the conversion is done in-place.
Method 2:
Another solution using predefined functions in Python 3:
Python3
# Python program to Remove # extra spaces from a stringinput_string = \ ' Hello Geeks . Welcome , Do you love Geeks , Geeks ? 'output_string = []space_flag = False # Flag to check if spaces have occurredfor index in range(len(input_string)): if input_string[index] != ' ': if space_flag == True: if (input_string[index] == '.' or input_string[index] == '?' or input_string[index] == ','): pass else: output_string.append(' ') space_flag = False output_string.append(input_string[index]) elif input_string[index - 1] != ' ': space_flag = Trueprint (''.join(output_string)) |
Output:
Hello Geeks. Welcome to neveropen. Do you love Geeks, Geeks?
Time complexity of above solution is O(n).
Auxiliary Space is O(n) as another list had to be created.
Method 3: (Using built-in function)
C++
#include <iostream>#include <string>#include <regex>int main() { std::string str = " Hello Geeks . Welcome , Do you love Geeks , Geeks ? "; // Use regular expression to replace multiple spaces with a single space std::regex pattern("\\s+"); std::string result = std::regex_replace(str, pattern, " "); // Remove leading and trailing spaces size_t firstNonSpace = result.find_first_not_of(" "); size_t lastNonSpace = result.find_last_not_of(" "); if (firstNonSpace != std::string::npos && lastNonSpace != std::string::npos) { result = result.substr(firstNonSpace, lastNonSpace - firstNonSpace + 1); } std::cout << result << std::endl; return 0;}// code contributed by shinjanpatra |
Java
/**Java Program to remove extra spaces from a string**/public class GFG { public static void main(String args[]) { String str = " Hello Geeks . Welcome , Do you love Geeks , Geeks ? "; System.out.println(str.replaceAll("\\s+"," ").trim()); }} |
Python3
# Python program to remove extra spaces from a string# Input stringstr = " Hello Geeks . Welcome , Do you love Geeks , Geeks ? "# Removing extra spaces using regeximport restr = re.sub('\s+', ' ', str).strip()# Printing the final stringprint(str) |
C#
// C# Program to remove// extra spaces from a stringusing System;class Program { static void Main(string[] args) { string str = " Hello Geeks . Welcome , Do you love Geeks , Geeks ? "; // Removing extra spaces using regex and print Console.WriteLine( System.Text.RegularExpressions.Regex.Replace( str.Trim(), @"\s+", " ")); }} |
Javascript
<script>// JavaScript Program to remove// extra spaces from a stringvar str = " Hello Geeks . Welcome , Do you love Geeks , Geeks ? ";document.write(str.replace("\\s+", " ").trim());// This code is contributed by rdtank</script> |
Output:
Hello Geeks . Welcome , Do you love Geeks , Geeks ?
Time Complexity: O(n), where n is the number of characters in the string.
Auxiliary Space: O(1), as there are only lowercase letters.
This article is contributed by Aarti_Rathi and Aditya Goel. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
