Rearrange Words in a Sentence

Rearrange Words in a Sentence

What is this problem about?

The Rearrange Words in a Sentence problem asks you to sort words in a sentence by their lengths, with ties maintaining their original relative order (stable sort), and format the result with the first letter capitalized and the rest lowercase. This medium coding problem tests stable sorting and string formatting. The sorting and string interview pattern is demonstrated.

Why is this asked in interviews?

Microsoft and Expedia ask this to test stable sort with custom comparators and string case manipulation. It validates clean tokenization, sorting, and reformatting skills.

Algorithmic pattern used

Lowercase all + stable sort by length + capitalize first word. Convert sentence to lowercase. Split into words. Stable sort by word length (using enumerate for stability in Python). Join with spaces. Capitalize the first letter.

Example explanation

s="Leetcode is cool". Lowercase: "leetcode is cool". Words: ["leetcode","is","cool"]. Sort by length (stable): ["is","cool","leetcode"] (lengths 2,4,8). Capitalize first: "Is cool leetcode". Result: "Is cool leetcode".

Common mistakes candidates make

• Not converting to lowercase first (mixed case causes sorting issues).
• Not performing a stable sort (ties must maintain original order).
• Capitalizing every word instead of just the first.
• Not handling single-word sentences.

Interview preparation tip

Rearrange Words in a Sentence emphasizes three sub-skills: tokenization, stable sort with custom key, and string formatting. Python's sort() is stable by default. For other languages, use index-based tiebreaking to achieve stability. Practice reformatting operations: always lower-then-process-then-capitalize to avoid case inconsistencies.