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:
- Primary: Increasing order of word length.
- Secondary: Original relative position for ties (stable sort requirement).
Key Constraints & Requirements:
- Input
textstarts 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^5chars): Solution must be efficient ( or ).
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 , where 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
- Split: Convert the
textinto a list of individual words using.split(). - 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.
- 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. - 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: to split the text where is the length of
text. Sorting takes where is the number of words. Since each word has at least one character, . Thus, sorting effectively operates within linear bounds relative to input size for practical purposes (specifically dominated by string operations). Overall: . - Space Complexity: We store the list of words and a new sorted list. This requires space proportional to the length of
text. Thus, 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
textcontains 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).