Rearrange Spaces Between Words in Java
In Java, string manipulation is a common task and one of such tasks is rearranging spaces between words inside a string, this operation involves adjusting the spaces between words either to make it confirm to a given format or pattern or to make it fit within a certain space and this operation may arise when formatting text or processing input data where the spacing between words needs to be changed.
Example 1:
Input
text = " this is a sentence "
Output
"this is a sentence"
Explanation
Total number of words: 4. Number of spaces between words = total spaces / (total words - 1) = 9 / (4 - 1) = 3 (integer division). Remaining spaces = total spaces % (total words - 1) = 9 % (4 - 1) = 0. Thus, there will be 3 spaces between each word.
Example 2:
Input
text = " practice makes perfect"
Output
"practice makes perfect "
Explanation
Total number of words: 3. Number of spaces between words = total spaces / (total words - 1) = 6 / (3 - 1) = 3 (integer division). Remaining spaces = total spaces % (total words - 1) = 6 % (3 - 1) = 0. Thus, there will be 3 spaces between each word.
Approach 1: Count and Reposition Approach
The Count and Reposition approach is a strategy for rearranging spaces between words in a string by counting the spaces and then redistributing them according to a specified pattern, this approach provides a simple yet effective solution for various text processing tasks.
Algorithm
Step 1: Initialize a variable spaceCount to 0. Iterate through each character c in the input string text.
Step 1.1: If c is a space, increment spaceCount by 1. Return spaceCount.
Step 2: Tokenization: Trim the input string text to remove leading and trailing spaces. Split the trimmed string into an array of words words using the regular expression \s+. Return words.
Step 3: Repositioning Spaces: Calculate the number of spaces needed between words (spacesBetweenWords) and any remaining spaces (remainingSpaces).
Step 3.1: Total number of words wordCount = length of words array. Total number of spaces spaceCount = result.
Step 4: If wordCount is greater than 1: spacesBetweenWords = spaceCount / (wordCount - 1). remainingSpaces = spaceCount % (wordCount - 1). Otherwise, set spacesBetweenWords to 0 and remainingSpaces to spaceCount.
Step 5: Initialize an empty StringBuilder rearrangedText. Iterate through each word in words with index i: Append the current word to rearrangedText.
Step 6: If i is less than wordCount - 1: Append spacesBetweenWords number of spaces to rearrangedText. Append remainingSpaces number of spaces to rearrangedText. Return rearrangedText as a string.
Filename: SpaceRearranger.java
import java.util.ArrayList;
import java.util.List;
public class SpaceRearranger {
// Function to rearrange spaces between words
public static String rearrangeSpaces(String text) {
// Step 1: Counting Spaces
int spaceCount = countSpaces(text);
// Step 2: Tokenization
String[] words = tokenize(text);
// Step 3: Repositioning Spaces
String rearrangedText = repositionSpaces(words, spaceCount);
// Step 4: Reconstructing the String
return rearrangedText;
}
// Step 1: Counting Spaces
private static int countSpaces(String text) {
int count = 0;
for (char c : text.toCharArray()) {
if (c == ' ') {
count++;
}
}
return count;
}
// Step 2: Tokenization
private static String[] tokenize(String text) {
return text.trim().split("\s+");
}
// Step 3: Repositioning Spaces
private static String repositionSpaces(String[] words, int spaceCount) {
int wordCount = words.length;
if (wordCount == 0) return "";
int spacesBetweenWords = (wordCount > 1) ? spaceCount / (wordCount - 1) : 0;
int remainingSpaces = (wordCount > 1) ? spaceCount % (wordCount - 1) : 0;
StringBuilder rearrangedText = new StringBuilder();
for (int i = 0; i < wordCount; i++) {
rearrangedText.append(words[i]);
if (i < wordCount - 1) {
rearrangedText.append(" ".repeat(spacesBetweenWords));
}
}
rearrangedText.append(" ".repeat(remainingSpaces));
return rearrangedText.toString();
}
public static void main(String[] args) {
// Example usage
String inputText = " practice makes perfect ";
String rearrangedText = rearrangeSpaces(inputText);
System.out.println("Original Text: " + inputText);
System.out.println("Rearranged Text: " + rearrangedText);
}
}
Output:
Original Text: practice makes perfect Rearranged Text: practice makes perfect
Time Complexity
The time complexity for counting spaces is O(n): which involves iterating through each character in the string and tokenization is O(n): Splitting the string into words involves a linear scan of the string, where n is the length of the input string. Therefore, the overall time complexity is O(n).
Space Complexity
The space complexity of Repositioning Spaces is: O(n), where n is the length of the resulting rearranged string. A StringBuilder or similar data structure is used to build the rearranged string, which requires space proportional to the length of the string and for counting spaces it is O(1). Therefore, the overall space complexity is O(n).