algoadvance

Leetcode 1592. Rearrange Spaces Between Words

Problem Statement

You are given a string text of words that are separated by spaces. Your task is to rearrange the spaces so that there is an equal number of spaces between each word and any extra spaces are placed at the end of the string.

For instance, consider the input string text = " this is a sentence ".

Your task is to partition the spaces as evenly as possible between the words, with any extra spaces flowing to the end.

Example

Input: text = "  this   is  a sentence "
Output: "this   is   a   sentence"

Constraints

  1. 1 <= text.length <= 100
  2. text consists of lowercase and uppercase English letters and ‘ ‘ (space) characters.
  3. There is at least one word in text.

Clarifying Questions

  1. Do we need to handle both leading and trailing spaces?
    • Yes, the extra spaces should be added to the end of the resultant string if they do not evenly divide among the words.
  2. Are words guaranteed to be separated by at least one space in the input?
    • Yes, they are separated by spaces as per the problem statement.

Strategy

  1. Split the input text into words using space as the delimiter.
  2. Count the number of spaces in the original text.
  3. Calculate the number of spaces needed between each word (evenlyDistributedSpaces).
  4. Calculate the remaining spaces that need to go at the end (remainingSpaces).
  5. Build the resultant string by joining the words with the computed number of spaces between each.
  6. Append the remaining spaces to the end of the resultant string.

Code

Here’s the complete implementation in Java:

public class Solution {
    public String reorderSpaces(String text) {
        // Split the text by spaces to get words
        String[] words = text.trim().split("\\s+");
        int totalSpaces = text.length() - text.replace(" ", "").length();
        int spaceBetweenWords = words.length > 1 ? totalSpaces / (words.length - 1) : 0;
        int extraSpaces = words.length > 1 ? totalSpaces % (words.length - 1) : totalSpaces;
        
        // Join words with `spaceBetweenWords` number of spaces.
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < words.length; i++) {
            if (i > 0) {
                for (int j = 0; j < spaceBetweenWords; j++) {
                    sb.append(' ');
                }
            }
            sb.append(words[i]);
        }
        
        // Add extra spaces at the end
        for (int i = 0; i < extraSpaces; i++) {
            sb.append(' ');
        }
        
        return sb.toString();
    }
}

Time Complexity

Therefore, the overall time complexity is O(n), where n is the length of the input string.

This is efficient given the constraint that the maximum length of text can be 100 characters.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI