interviewing.io
EASY
DATA STRUCTURES AND ALGORITHMS

How to solve the Reverse Words in a String Problem

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

Introduction Reverse Words in a String

The Reverse Words in a String problem offers a straightforward task of taking a string of words as input and returning 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.

Problem Reverse Words in a String

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 Inputs and Outputs

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

Solution Reverse Words in a String

Watch Someone Solve Reverse Words in a String
Microsoft InterviewPython Interview
Advance this person to the next round?
Thumbs up
Technical Skills:
3/4
Problem Solving Ability:
3/4
Communication Ability:
4/4
Show Transcript
More Details
New Tab

Problem Approaches

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

As with many problems, this specific problem can be tackled similar to how we would likely approach it if we were solving it 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 and trim/eliminate the unneeded space between words, at the beginning of the string and at the end of the string 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 cannot 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 Questions Similar to Reverse Words in a String

MEDIUM
Data Structures and Algorithms
Build a Max Heap

Given an array of integers, transform the array in-place to a max heap.

Watch 1 interview
MEDIUM
Data Structures and Algorithms
Three Sum

Given an array of integers, return an array of triplets such that i != j != k and nums[i] + nums[j] + nums[k] = 0.

Watch 1 interview
EASY
Data Structures and Algorithms
Reverse Linked List

Given the head of a linked list, reverse the list and return the new head.

Watch 2 interviews

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.

Ready to practice with a mock interview?

Book mock interviews with engineers from Google, Facebook, Amazon, or other top companies. Get detailed feedback on exactly what you need to work on. Everything is fully anonymous.