EASY
DATA STRUCTURES AND ALGORITHMS

How to Solve Reverse Words in a String

Written By
tom-wagner.png
Tom Wagner
kenny-polyack.png
Kenny Polyak

What is the Reverse Words in a String Problem?

Reverse Words in a String is a programming problem that requires you to take a string of words and return a new string with the order of the words reversed. This problem invites us to use native string and array methods, by looping over the input string in reverse and building a new string to return, and can even be done in-place using languages that permit string mutation.

An Example of the Reverse Words in a String Problem

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

Note that the input string s may contain multiple spaces between any given two words, as well as leading or trailing spaces; however, the return sentence should only have a single space between all words and should not have any leading or trailing space.

Example 1 Input: s = “This sentence is forwards” Output: “forwards is sentence This”

Input: s = “ a blue whale rhino Boston arepa heaven “ Output: s = “heaven arepa Boston rhino whale blue a“

Constraints

  • The string will only contain upper-case and lower-case letters (no punctuation)
  • 1 <= s.length <= 10,000

Solutions to the Reverse Words in a String Interview Question

There are two methods for reversing words in a string. One method is splitting on spaces, reversing the list and joining. Alternatively, you can reverse the string in place.

Approach 1: Split on Spaces, Reverse the List and Join

This specific problem can be tackled in a manner similar to how we'd approach it if we were solving manually (remember, in an interview setting you always want to communicate your strategy, especially for multi-step solutions like this):

Identify all the individual words at the beginning and end of the string, and then trim/eliminate the unneeded space. Reverse the order of the words and build the string back up to form the result.

Diving into the code, most modern programming languages provide a standard library method to split a string on a given character, in this case ” “.

Reverse Words in a String Python and Ruby Solutions - Split on Spaces, Reverse the List and Join

s = “ this is a  string  “
words = s.split(“ “)
print(words) # ['', 'this', 'is', '', 'a', 'string', '', '']

When we use this method, note how both trailing and leading spaces end up in the words list as empty strings. We can then filter the words list in order to remove the empty strings:

words = s.split(“ “)
filtered_words = [s for s in words if s != '']
print(filtered_words) # ['this', 'is', 'a', 'string']

All we have left to do now is reverse the list and join the words with a space between them, and in the end we have a fairly straightforward algorithm.

class Solution:
    def reverseWords(self, s: str) -> str:
        words = s.split(' ')
        filtered_words = [s for s in words if s != '']
        return ' '.join(filtered_words[::-1])

Time/Space Complexity

  • Time complexity: O(n), as the interpreter iterates over the input string once and the list of words twice.
  • Space complexity: O(n), to store the list of words after splitting by spaces.

Approach 2: In-place

Let’s pretend that you find yourself in an interview and your interviewer has asked a follow up question: “Is it possible to solve this problem and be more efficient from a space complexity standpoint?”

We already know our first solution is O(n), leaving O(log(n)) and O(1) as the two most common ways to improve. A log(n) algorithm is most often related to dividing and conquering or binary search, and neither of those concepts apply here. So how can we make our solution constant space? We aren’t allowed extra memory, so the only way to do so is by mutating the string in place.

Depending on the coding language being used, strings are either mutable or immutable. If a given language has immutable strings this means that the string can't be edited in-place without creating a new string in memory (which is a O(n) operation, with n being the length of the string). Conversely, if a given language has mutable strings that means the string can be edited in-place, similar to an array/list.

For example, in Ruby:

s = ‘0123456789’ # note this is a string
s[1..8] = s[1..8].reverse
 
# the ruby version of print() or console.log()
puts s # ‘0876543219’, as ‘12345678’ has been reversed in-place

To read more about mutable vs immutable strings, check out this article on the topic by MIT.

If coding in a language with immutable strings (Python, Javascript, Java, etc.) mutating the string will not work, however there may be classes or libraries (such as Stringbuilder in Java) that would allow you to employ a similar approach - an interviewer may let you just assume you have one of these imported.

To mutate the string in place the algorithm can again be broken down into multiple steps:

  1. Identify the distinct words by iterating over the string looking for spaces
  2. Reverse the words in place one word at a time, trimming/skipping extra spaces while iterating
  3. Trim any unneeded space from the end of the string

Reverse Words in a String Ruby Solution - In-place String Mutation

def reverse_words(s)
    s.reverse!
    
    l = 0
    r = 0
    i = 0
    n = s.length
    
    while i < n
        
        # find the next space
        while i < n and s[i] != ' '
            s[r] = s[i]
            r += 1
            i += 1
        end
        
        if l < r
            # reverse the current word
            s[l..r-1] = s[l..r-1].reverse
            
            s[r] = ' '
            r += 1
            l = r
        end
        
        i += 1
    end
    
    # trim end of string since we have shuffled string to the left
    s.slice!(r..s.length)
    
    s.strip!
    
    return s
    
end

Time/Space Complexity

  • Time complexity: O(n), as we iterate over the string with multiple pointers but only do one iteration of each pointer.
  • Space complexity: O(1)

Practice the Reverse Words in a String Problem With Our AI Interviewer

Start AI Interview

Reverse Words in a String Frequently Asked Questions (FAQ)

How do you reverse each word in a string?

There are two approaches you can take. The first is to split the string on spaces, reverse each word individually (see our in-depth solution to “reverse a string”), and then join them back. This approach runs in O(n) time and requires O(n) space.

A more space-efficient solution is to reverse the entire sentence in place. Note that this approach only works in languages where strings are mutable. To mutate the string in place, you would identify words by iterating over the string looking for spaces. Then you’d reverse the words in place one word at a time. Finally you’d trim any unneeded spaces from the end of the string.

This solution still runs in linear time but requires only constant space.

Why can’t I just use the reverse() function to solve this problem?

You can… if you’re implementing sentence reversal in the real world. In an interview, however, you need to show your interviewer that you know how built-in functions work under the hood – that’s part of why interviewers ask questions like this.

How do you reverse each word in a string in Python?

Because strings are immutable in Python, you wouldn’t be able to reverse the string in place. As such, you can use the approach where you split the string on spaces, reverse each word, and then join them back, like so:

def reverseWords(self, s: str) -> str:
3        words = s.split(' ')
4        filtered_words = [s for s in words if s != '']
5        return ' '.join(filtered_words[::-1])

About interviewing.io

interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.

We know exactly what to do and say to get the company, title, and salary you want.

Interview prep and job hunting are chaos and pain. We can help. Really.