Rearrange Spaces Between Words

Easy

Asked by:

6 views

Topics:

Strings

You are given a string text of words that are placed among some number of spaces. Each word consists of one or more lowercase English letters and are separated by at least one space. It's guaranteed that text contains at least one word.

Rearrange the spaces so that there is an equal number of spaces between every pair of adjacent words and that number is maximized. If you cannot redistribute all the spaces equally, place the extra spaces at the end, meaning the returned string should be the same length as text.

Return the string after rearranging the spaces.

Example 1:

Input: text = "  this   is  a sentence "
Output: "this   is   a   sentence"
Explanation: There are a total of 9 spaces and 4 words. We can evenly divide the 9 spaces between the words: 9 / (4-1) = 3 spaces.

Example 2:

Input: text = " practice   makes   perfect"
Output: "practice   makes   perfect "
Explanation: There are a total of 7 spaces and 3 words. 7 / (3-1) = 3 spaces plus 1 extra space. We place this extra space at the end of the string.

Constraints:

1 <= text.length <= 100
text consists of lowercase English letters and ' '.
text contains at least one word.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Will the input string always contain at least one word? What should I return if the input string is empty or contains only spaces?
If the spaces cannot be distributed evenly, how should I handle the extra spaces? Should they be distributed to the left or right?
Can the input string contain leading or trailing spaces? Should I trim them before processing?
What is the expected return type? Should I return a new string, or modify the input string in place (if that was possible)?
Are there any constraints on the length of the words in the input string?

Brute Force Solution

Approach

The brute force method for rearranging spaces is like trying out every single way you could possibly distribute the spaces between the words. We essentially test every single arrangement and choose the best one. It's thorough, but not very efficient.

Here's how the algorithm would work step-by-step:

First, figure out how many spaces you have in total to distribute.
Then, consider all possible numbers of spaces to put between each pair of words. This means trying one space between each word, then two spaces, then three, and so on.
For each possible arrangement of spaces between words, check if using that number of spaces results in the total number of spaces matching the number you have to distribute.
If the number of spaces used doesn't match the number you have, discard that possibility.
If the numbers match, see if the arrangement fits within the allowed length. This might depend on the specific rules of the problem.
Keep track of all arrangements of spaces that both use the right number of spaces and are valid according to length constraints or other rules.
Once you have tried every possible arrangement, pick the 'best' one from the arrangements you saved. What 'best' means depends on the problem's specific rules, such as maximizing spaces at the end.

Code Implementation

def rearrange_spaces_brute_force(text):    words = text.split()    number_of_words = len(words)
    number_of_spaces = text.count(' ')
    best_arrangement = ""
    for spaces_between_words in range(1, number_of_spaces + 1):        # Check if this arrangement is possible.        if number_of_words == 1 and spaces_between_words != number_of_spaces:            continue
        if number_of_words > 1 and (number_of_words - 1) * spaces_between_words > number_of_spaces:            continue
        extra_spaces = number_of_spaces - (number_of_words - 1) * spaces_between_words if number_of_words > 1 else number_of_spaces        if number_of_words == 1:
            arrangement = words[0] + ' ' * extra_spaces
        else:
            arrangement = (' ' * spaces_between_words).join(words) + ' ' * extra_spaces

        # This is the only valid arrangement so far.        best_arrangement = arrangement    return best_arrangement

Big(O) Analysis

Time Complexity

O(n!) – The provided brute force approach explores all possible arrangements of spaces. If there are 'n' total characters in the input string and 'w' words, the algorithm essentially tries all possible combinations of spaces between the words. The number of ways to distribute 's' spaces among 'w-1' gaps can be calculated using combinations, which grows factorially with the number of spaces and words. Because we are effectively iterating through a large subset of all possible permutations of space arrangements, the time complexity is approximated by O(n!), where 'n' is related to the total number of characters in the input and determines the size of the space arrangement problem being explored.

Space Complexity

O(N) – The brute force approach considers all possible arrangements of spaces. To keep track of potentially valid arrangements, we need to store them, which could involve building new strings or storing intermediate results. In the worst-case scenario, we might store multiple arrangements, each potentially as long as the original string. Thus, the space complexity is proportional to the length of the input string, N, because the number of arrangements to keep track of can grow linearly with the input string length. This leads to an auxiliary space complexity of O(N).

Optimal Solution

Approach

The best way to rearrange spaces is to figure out how many gaps you need to fill and how many spaces you have. Then, evenly distribute the spaces among the gaps. Finally, handle the case where the spaces don't divide evenly or if there's only one word.

Here's how the algorithm would work step-by-step:

First, count the number of words and the total number of spaces in the input.
If there's only one word, add all the spaces to the right of it and you're done.
If there are multiple words, calculate how many spaces to put between each pair of words by dividing the total spaces by the number of gaps between words. The number of gaps is always one less than the number of words.
Calculate the remainder - the extra spaces that can't be evenly distributed.
Create the final string by putting the calculated number of spaces between each word.
Add any remaining spaces to the end of the string after the last word.

Code Implementation

def rearrange_spaces(text: str) -> str:
    words = text.split()
    number_of_words = len(words)
    number_of_spaces = text.count(' ')

    if number_of_words == 1:
        return words[0] + ' ' * number_of_spaces

    # Calculate spaces between words.
    spaces_between = number_of_spaces // (number_of_words - 1)

    # Determine the remaining spaces after even distribution.
    remaining_spaces = number_of_spaces % (number_of_words - 1)

    result = ''
    for i in range(number_of_words - 1):
        result += words[i] + ' ' * spaces_between

    result += words[-1] + ' ' * remaining_spaces
    return result

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string once to count words and spaces, where n is the length of the input string. Subsequently, it constructs the output string by iterating through the words, inserting calculated spaces between them and appending remaining spaces. These are linear operations relative to the number of words which, in the worst case, is bounded by the length of the original string. Thus, the dominant operation is iterating through the input string once, making the time complexity O(n).

Space Complexity

O(N) – The algorithm constructs a new string to store the rearranged words and spaces. The size of this new string depends on the length of the input string, which we denote as N. In the worst case, the new string will have the same number of characters as the original input string if we consider a single word followed by many spaces which get redistributed. Therefore, the auxiliary space used is proportional to N, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty input string	Return an empty string immediately since there are no words to rearrange.
Input string with only spaces	Return the original string if it contains only spaces since there are no words to rearrange.
Input string with a single word	Append the remaining spaces after the single word.
Input string with leading and trailing spaces	Trim the leading and trailing spaces before processing the string to avoid incorrect word and space counts.
Input string with multiple spaces between words	Normalize spaces to a single space between words during word extraction to ensure accurate word count and space distribution.
Zero spaces in the input	If no spaces exist in the input (e.g., a single word), return the word itself.
Large input string that may cause memory issues.	Use a StringBuilder instead of string concatenation for better memory efficiency.
Input has a very large number of words with a very small number of spaces.	Ensure that the integer division for space distribution doesn't result in incorrect calculation due to overflow or precision issues by using appropriate data types.

Empty input string

How to Handle:

Return an empty string immediately since there are no words to rearrange.

Input string with only spaces

How to Handle:

Return the original string if it contains only spaces since there are no words to rearrange.

Input string with a single word

How to Handle:

Append the remaining spaces after the single word.

Input string with leading and trailing spaces

How to Handle:

Trim the leading and trailing spaces before processing the string to avoid incorrect word and space counts.

Input string with multiple spaces between words

How to Handle:

Normalize spaces to a single space between words during word extraction to ensure accurate word count and space distribution.

Zero spaces in the input

How to Handle:

If no spaces exist in the input (e.g., a single word), return the word itself.

Large input string that may cause memory issues.

How to Handle:

Use a StringBuilder instead of string concatenation for better memory efficiency.

Input has a very large number of words with a very small number of spaces.

How to Handle:

Ensure that the integer division for space distribution doesn't result in incorrect calculation due to overflow or precision issues by using appropriate data types.