algoadvance

Leetcode 1592. Rearrange Spaces Between Words

Problem Statement

Given a string text of words and spaces, rearrange the spaces such that:

1. There is an equal number of spaces between every pair of adjacent words.
2. If there are extra spaces left after distributing evenly, put them at the end.

Return the resultant string after redistribution.

Clarifying Questions

1. Input Constraints:
   • The input string text consists of lowercase English letters and spaces.
   • 1 <= text.length <= 100.
2. Edge Cases:
   • Multiple spaces between words.
   • A single word with spaces.
   • Only spaces.

Strategy

1. Count the Total Spaces: Use a loop to count spaces in the text.
2. Extract Words: Use string stream to split the words from text.
3. Calculate Spaces Distribution:
   • If there’s only one word, all spaces should be appended after the word.
   • For more than one word, calculate the number of spaces to distribute evenly between words and the remaining spaces to append at the end.
4. Build the Resulting String: Insert the calculated number of spaces between words and append the remaining spaces at the end if any.

Code

Here’s the C++ code for solving the problem:

#include <iostream>
#include <vector>
#include <sstream>

std::string reorderSpaces(std::string text) {
    int totalSpaces = 0, n = text.size();
    for (char c : text) {
        if (c == ' ')
            totalSpaces++;
    }

    std::vector<std::string> words;
    std::istringstream ss(text);
    std::string word;
    while (ss >> word) {
        words.push_back(word);
    }

    int numWords = words.size();
    if (numWords == 1) {
        // Only one word, all spaces go at the end
        return words[0] + std::string(totalSpaces, ' ');
    } else {
        int spacesBetween = totalSpaces / (numWords - 1);
        int extraSpaces = totalSpaces % (numWords - 1);
        
        std::string result;
        for (int i = 0; i < numWords; i++) {
            result += words[i];
            if (i != numWords - 1) {
                result += std::string(spacesBetween, ' ');
            }
        }
        // Append the remaining spaces
        result += std::string(extraSpaces, ' ');

        return result;
    }
}

Time Complexity

• O(N): Here N is the length of the text.
  • We traverse the text once to count spaces.
  • Another linear pass to extract words.
  • Assembling the result takes linear time in terms of the number of characters and words.
• Space complexity is linear in terms of words extraction and the resultant string creation.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?