Domain 2MediumMEDIUM

Rearrange Words in a Sentence

Split the sentence into words, normalize casing to lowercase, sort by length using a stable sort algorithm (preserving original order for ties), and reconstruct the string with proper capitalization.

Domain: medium•Updated: 2026-09-16
#sorting#string-manipulation#o(n-log-n)#stable-sort

Problem Breakdown

We are given a sentence text consisting of space-separated words. The input guarantees that only single spaces separate words and the first letter is uppercase (sentence case format). The goal is to reorder these words based on two criteria:

  1. Primary: Increasing order of word length.
  2. Secondary: Original relative position for ties (stable sort requirement).

Key Constraints & Requirements:

  • Input text starts with a capital letter, followed by lowercase letters and single spaces.
  • Output must follow the same format: First character uppercase, rest lowercase. This implies we need to normalize casing before sorting/reordering because examples show internal words losing their original case (e.g., “Leetcode” becomes “leetcode”).
  • Return type is a string representing the rearranged sentence.

Edge Cases:

  • Single word input: Should remain unchanged except for ensuring correct capitalization format.
  • All words same length: Must preserve exact original order due to stable sort requirement.
  • Large inputs (10^5 chars): Solution must be efficient (O(N)O(N) or O(Wlog⁡W)O(W \log W)).

Intuition

A brute force approach would involve generating all permutations of the word list and checking which one satisfies the length constraint, then capitalizing correctly. This is factorial time complexity O(W!)O(W!), where WW is the number of words—completely infeasible for large inputs.

The key insight here is that sorting provides a direct way to satisfy the ordering constraints. Since Python’s built-in sort or sorted() function uses Timsort (a stable sort algorithm), we can simply provide a custom key based on word length without needing an explicit secondary index, as ties will automatically retain their original relative order.

The casing requirement simplifies our logic: instead of trying to preserve complex input casing rules during sorting, we normalize all words to lowercase immediately after splitting. This ensures consistency. We only apply the capitalization rule at the very end on the resulting string (first letter uppercase).

Approach

  1. Split: Convert the text into a list of individual words using .split().
  2. Normalize: Iterate through the word list and convert every word to lowercase. This handles the requirement that output casing is uniform except for the first letter, regardless of input variations.
  3. Sort: Sort this normalized list based on len(word). Because Python’s sort is stable, words with equal lengths will remain in their original relative order automatically.
  4. Join & Format: Join the sorted list back into a single string using spaces as separators. Finally, capitalize the first character of the resulting sentence and ensure the rest are lowercase (which they already are from step 2).

Complexity Analysis

  • Time Complexity: O(N)O(N) to split the text where NN is the length of text. Sorting takes O(Wlog⁡W)O(W \log W) where WW is the number of words. Since each word has at least one character, W≤NW \le N. Thus, sorting effectively operates within linear bounds relative to input size for practical purposes (specifically dominated by string operations). Overall: O(N+Wlog⁡W)O(N + W \log W).
  • Space Complexity: We store the list of words and a new sorted list. This requires space proportional to the length of text. Thus, O(N)O(N) auxiliary space is used for storage (excluding input/output strings).

Solution

def arrangeWords(text: str) -> str:
    # Split text into individual words based on spaces
    words = text.split()
    
    # Normalize all words to lowercase. 
    # This ensures consistent casing in the output regardless of original capitalization,
    # except for the very first letter which we will handle at the end.
    normalized_words = [word.lower() for word in words]
    
    # Sort by length. Python's sort is stable, so ties preserve original order.
    sorted_words = sorted(normalized_words, key=len)
    
    # Join the sorted words back into a sentence with single spaces
    result = " ".join(sorted_words)
    
    # Capitalize only the first letter of the resulting string to match format requirements
    if len(result) > 0:
        return result[0].upper() + result[1:]
        
    return ""

# Example usage for verification (not part of function signature):
# print(arrangeWords("Leetcode is cool")) # Output: "Is cool leetcode"

Edge Cases Handled

  • Single Word: If text contains only one word, the split list has length 1. Sorting does nothing to order. The join returns that single word. Capitalization logic ensures it starts with an uppercase letter (e.g., “Hello”).
  • Tie-Breaking Stability: Since we rely on Python’s stable sort algorithm (sorted), words of identical length are not reordered relative to their appearance in the input list, satisfying the requirement for original order preservation.
  • Casing Normalization: By lowercasing all tokens before sorting and joining, we avoid issues where a word like “Is” might be treated differently than “is”. We enforce the output format (only first letter upper) at the very end to ensure strict compliance with examples provided in the problem description.
  • Empty Input Handling: Although constraints imply text.length >= 1, the code includes a check for empty result length before capitalizing, preventing index errors if an edge case of zero-length string were passed (though not expected per constraints).