Reverse Words in a String

Reverse Words in a String is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Two Pointers pattern, in the String Reversal subpattern.

Problem statement

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:

- 1 <= s.length <= 104

- s contains English letters (upper-case and lower-case), digits, and spaces ' '.

- There is at least one word in s.

Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?

Topics and companies

Topics: Two Pointers, String.

Reported in interviews at Microsoft, Oracle, LinkedIn, Apple, Salesforce.

How to practise Reverse Words in a String on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N), where N is the length of the input string. We scan the string once to extract words and once to build the result. time and O(N), for storing the words and the output string. space.

Open Reverse Words in a String in the code editor, or read the Reverse Words in a String editorial for a worked solution with its approach and complexity analysis.

Where Reverse Words in a String sits in the DSA pattern sheet

• Two Pointers pattern guide
• String Reversal subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Reverse Words in a String

Other problems that use the same String Reversal and Two Pointers techniques:

• Reverse String — Easy, same subpattern
• Reverse String II — Easy, same subpattern
• Reverse Vowels of a String — Easy, same subpattern
• Backspace String Compare — Easy, same pattern
• Boats to Save People — Medium, same pattern
• Container With Most Water — Medium, same pattern