1592. Rearrange Spaces Between Words

EasyString
Leetcode Link

Problem Description

In this problem, you are given a string text which consists of some words separated by some number of spaces. Each word is composed of lowercase English letters. The aim is to rearrange the spaces in such a way that there is an equal number of spaces between every pair of adjacent words, and the number of spaces between words should be as large as possible. If it is not possible to distribute spaces equally between words, any extra spaces should be added to the end of the result string. It's important to note that the resulting string should have the same length as the input string text, meaning that no spaces are added or removed beyond the initial allocation in text.

Intuition

Upon examining the problem, the first step is to determine how many spaces there are and how many words there are in the input string text. This is important because in order to distribute the spaces evenly, you need to know these counts.

The solution involves a few key steps:

  • Count the total number of spaces in the string, which can be simply done using the string method count().
  • Split the string into words, using the string method split(), to find out the number of individual words.

Now, there are two scenarios to consider:

  1. If there's only one word in the text, you cannot distribute spaces between words, so you just need to append all the spaces at the end of this single word.
  2. If there is more than one word, calculate how many spaces should be distributed between each pair of words. This is done by dividing the total number of spaces by one less than the number of words (since spaces go between words). The modulus operator helps calculate the number of extra spaces that cannot be evenly distributed and thus should be placed at the end.

In mathematical terms, if cnt is the number of spaces and m is the number of gaps between words (one less than the number of words), then each gap will have cnt // m spaces, and the end of the string will have cnt % m spaces left over.

Finally, the solution will be to join the words with the calculated number of spaces between them and append any remaining spaces at the end.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following is a good use case for backtracking?

Solution Approach

The implementation of the solution is straightforward and employs basic string manipulation methods available in Python. The solution does not resort to complex algorithms or data structures, as the problem itself is addressed with simple arithmetic and string operations. Here is the step-by-step breakdown of the solution approach:

  1. First, we count the total number of spaces in the input string text using the count() method. This is stored in the variable cnt.

    1cnt = text.count(' ')

  2. Next, we need to split text into words by using the split() method which by default splits by whitespace. The resulting list of words is stored in the variable words.

    1words = text.split()

  3. We calculate the number of gaps between the words as one less than the number of words. This is because spaces are only between words and not after the last word (unless there are extra spaces that couldn't be distributed evenly).

    1m = len(words) - 1

  4. The algorithm considers a special case where there is only one word. If m is 0 (i.e., no gaps because there's just one word), then all spaces should be appended to this single word and returned.

    1if m == 0:
2    return words[0] + ' ' * cnt

  5. If there is more than one word, we have to calculate the number of spaces to place between each word. We do this by integer division of the total spaces by the number of gaps m. This gives us the evenly distributed spaces between words.

    1' ' * (cnt // m)

  6. We also calculate the remainder of the spaces which will be added at the end of the string by using the modulus operator cnt % m. This will give us the extra spaces that cannot be evenly divided between words.

    1' ' * (cnt % m)

  7. Lastly, we join the words with calculated spaces between them and append any extra spaces at the end to get the final rearranged string. This is done by joining the list of words with the string of spaces corresponding to cnt // m, then appending the leftover spaces.

    1return (' ' * (cnt // m)).join(words) + ' ' * (cnt % m)

This concise yet effective approach guarantees that spaces are maximized between words, and any that cannot be evenly distributed are placed at the end, adhering to the problem's conditions, while ensuring the resulting string is the same length as the given text.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Example Walkthrough

Let's consider the input string text as "a b c d ". We can walk through the solution approach step-by-step using this example:

  1. First, we count the number of spaces in the input string. The text "a b c d " has 6 spaces.

  2. Next, we split text into words, resulting in ["a", "b", "c", "d"]. We have 4 words here.

  3. Now we calculate the number of gaps between the words. Since we have 4 words, there will be 4 - 1 = 3 gaps between them.

  4. Since we have 3 gaps and 6 spaces, and we want the maximum number of evenly distributed spaces between words, we divide the number of spaces by the number of gaps. So, 6 // 3 = 2 spaces should be between each word.

  5. We calculate the remainder of the spaces by using the modulus operator. There are no extra spaces since 6 % 3 = 0.

  6. Finally, we join the words with the calculated number of spaces between them, which in this case is 2 spaces. So the final string will be "a b c d", and there are no extra spaces left to append at the end.

By following the approach, we have restructured the original text to have an equal number of spaces between each pair of adjacent words and managed to keep the string length unchanged.

Solution Implementation

1class Solution:
2    def reorderSpaces(self, text: str) -> str:
3        # Count the number of spaces in the input text
4        space_count = text.count(' ')
5      
6        # Split the text by spaces to get words
7        words = text.split()
8      
9        # Calculate the number of spaces to be inserted between words
10        num_spaces_between_words = len(words) - 1
11      
12        # If there's only one word, we append all spaces after the word
13        if num_spaces_between_words == 0:
14            return words[0] + ' ' * space_count
15      
16        # Compute the number of spaces to distribute evenly between words
17        spaces_to_distribute = space_count // num_spaces_between_words
18        # And compute the remaining spaces to put at the end
19        remaining_spaces = space_count % num_spaces_between_words
20      
21        # Join the words with evenly distributed spaces and append the remainder at the end
22        return (' ' * spaces_to_distribute).join(words) + ' ' * remaining_spaces
23
1class Solution {
2    public String reorderSpaces(String text) {
3        // Count the total spaces in the input text
4        int spaceCount = 0;
5        for (char c : text.toCharArray()) {
6            if (c == ' ') {
7                spaceCount++;
8            }
9        }
10      
11        // Split the text into words, ignoring multiple spaces between words
12        String[] wordsArray = text.trim().split("\\s+"); // Trim helps to avoid empty strings at the start and end
13      
14        // Filter out any empty strings from the words array and add them to a list
15        List<String> wordsList = new ArrayList<>();
16        for (String word : wordsArray) {
17            if (!word.isEmpty()) {
18                wordsList.add(word);
19            }
20        }
21      
22        // Determine the number of gaps between words (slots for spaces)
23        int numberOfGaps = wordsList.size() - 1;
24      
25        // Handle edge case with only one word by appending all spaces at the end
26        if (numberOfGaps == 0) {
27            return wordsList.get(0) + " ".repeat(spaceCount);
28        }
29      
30        // Calculate spaces to distribute between words and at the end
31        int spacesBetweenWords = spaceCount / numberOfGaps;
32        int extraSpacesAtEnd = spaceCount % numberOfGaps;
33      
34        // Join the words with evenly distributed spaces
35        String evenlySpacedText = String.join(" ".repeat(spacesBetweenWords), wordsList);
36      
37        // Add leftover spaces to the end of the text
38        evenlySpacedText += " ".repeat(extraSpacesAtEnd);
39      
40        // Return the formatted text
41        return evenlySpacedText;
42    }
43}
44
1#include <string>
2#include <sstream>
3#include <vector>
4
5std::string reorderSpaces(std::string text) {
6    // Count the total number of spaces in the text
7    int spaceCount = 0;
8    for (char ch : text) {
9        if (ch == ' ') {
10            spaceCount++;
11        }
12    }
13
14    // Split the text into words
15    std::vector<std::string> words;
16    std::istringstream stream(text);
17    std::string word;
18
19    while (stream >> word) {
20        words.push_back(word);
21    }
22
23    int numWords = words.size();
24
25    // If there is only one word, append all the spaces at the end
26    if (numWords == 1) {
27        return words[0] + std::string(spaceCount, ' ');
28    }
29
30    // Calculate the number of spaces to distribute between words
31    int spacesBetweenWords = spaceCount / (numWords - 1);
32
33    // Calculate the number of spaces to be added at the end
34    int trailingSpacesCount = spaceCount % (numWords - 1);
35
36    // Construct the string with evenly distributed spaces
37    std::string result;
38    for (int i = 0; i < numWords; ++i) {
39        result += words[i];
40        if (i < numWords - 1) { // No need to add spaces after the last word
41            result += std::string(spacesBetweenWords, ' ');
42        }
43    }
44  
45    // Append the trailing spaces
46    result += std::string(trailingSpacesCount, ' ');
47
48    return result;
49}
50
1function reorderSpaces(text: string): string {
2    // Count the total number of spaces in the text
3    let spaceCount = 0;
4    for (const char of text) {
5        if (char === ' ') {
6            spaceCount++;
7        }
8    }
9
10    // Split the text into words, ignoring multiple spaces
11    const words = text.trim().split(/\s+/);
12    const numWords = words.length;
13
14    // If there is only one word, append all the spaces at the end
15    if (numWords === 1) {
16        return words[0] + ' '.repeat(spaceCount);
17    }
18
19    // Calculate the number of spaces to distribute between words
20    const spacesBetweenWords = Math.floor(spaceCount / (numWords - 1));
21
22    // Calculate the number of spaces to be appended to the end of the result
23    const trailingSpacesCount = spaceCount % (numWords - 1);
24
25    // Join the words with the spaces in-between and append trailing spaces
26    return words.join(' '.repeat(spacesBetweenWords)) + ' '.repeat(trailingSpacesCount);
27}
28
Not Sure What to Study? Take the 2-min Quiz：

Which type of traversal does breadth first search do?

Time and Space Complexity

The time complexity of the code is O(n) where n is the length of the input string text. This time complexity stems from the two main operations in the function:

  1. Counting the number of spaces with text.count(' '), which iterates over each character in the input string once.

  2. Splitting the string into words with text.split(), which also iterates over each character in the input string to find word boundaries and split the words accordingly.

Each of these operations is linear with respect to the length of the input string, and since they are not nested, the overall time complexity remains linear.

The space complexity of the code is also O(n). This is because the words list is created by splitting the input text, and in the worst case (when all characters in the input are words and no multiple consecutive spaces), this list could contain a copy of every character in the input string. Additionally, during the join operation, a new string which is roughly the same size as the input string is created to accommodate the reordered words and spaces.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫