Is Reverse Words in a String easy or hard?

The problem is rated Medium because it requires careful handling of spaces and string boundaries. The basic idea of reversing words is straightforward, but implementing the in-place version with correct pointer movement and space trimming adds moderate complexity.

How to solve Reverse Words in a String in O(n)?

Traverse the string once to extract words or clean spaces, then reverse their order. With the split method, split the string into words, reverse the list, and join with spaces. With the in-place method, reverse the entire string and then reverse each word using two pointers. Both methods ensure every character is visited only a few times, giving O(n) time.

Reverse Words in a String Python or Java solution

In Python, the simplest solution uses `" ".join(reversed(s.split()))`, which splits the string into words and joins them in reverse order. In Java, you can use `String.split()` to create an array of words, reverse the array, and rebuild the string using `StringBuilder`. Both implementations run in O(n) time.

What is the best approach for Reverse Words in a String?

Two common solutions exist. The easiest is the split-and-reverse approach where you split the string into words, reverse the list, and join them back together. This runs in O(n) time and O(n) space. A more optimized method reverses the entire character array and then reverses each word using two pointers, achieving O(n) time and O(1) extra space.

Is Reverse Words in a String asked at Google/Amazon/Meta?

Reverse Words in a String appears frequently in interviews at large tech companies because it tests string manipulation and pointer logic. Variants of the problem have been reported in interviews at Amazon, Google, Meta, and Microsoft. Interviewers often expect candidates to handle edge cases like extra spaces and in-place transformations.

What data structure is used in Reverse Words in a String?

The split-and-reverse approach uses a dynamic array or list to store words temporarily. The optimized approach works directly on a character array and uses two pointers to reverse segments in place. Both solutions rely primarily on string processing and pointer traversal.

What is the time complexity of Reverse Words in a String?

The optimal time complexity is O(n), where n is the length of the string. Each character is processed a constant number of times during splitting, reversing, or pointer traversal. Both the split-and-reverse approach and the in-place reversal method achieve linear time complexity.

Description Solution Video 13:58

151. Reverse Words in a String

Medium57.8% acceptance30 companies

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: s = "  hello world  "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: s = "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Constraints: