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.
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
1 <= s.length <= 10,000
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 ” “
.
s = “ this is a string “
words = s.split(“ “)
print(words) # ['', 'this', 'is', '', 'a', 'string', '', '']
1s = “ this is a string “
2words = s.split(“ “)
3print(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']
1words = s.split(“ “)
2filtered_words = [s for s in words if s != '']
3print(filtered_words) # ['this', 'is', 'a', 'string']
4
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])
1class Solution:
2 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])
6
O(n)
, as the interpreter iterates over the input string once and the list of words twice.O(n)
, to store the list of words after splitting by spaces.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
1s = ‘0123456789’ # note this is a string
2s[1..8] = s[1..8].reverse
3
4# the ruby version of print() or console.log()
5puts s # ‘0876543219’, as ‘12345678’ has been reversed in-place
6
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:
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
1def reverse_words(s)
2 s.reverse!
3
4 l = 0
5 r = 0
6 i = 0
7 n = s.length
8
9 while i < n
10
11 # find the next space
12 while i < n and s[i] != ' '
13 s[r] = s[i]
14 r += 1
15 i += 1
16 end
17
18 if l < r
19 # reverse the current word
20 s[l..r-1] = s[l..r-1].reverse
21
22 s[r] = ' '
23 r += 1
24 l = r
25 end
26
27 i += 1
28 end
29
30 # trim end of string since we have shuffled string to the left
31 s.slice!(r..s.length)
32
33 s.strip!
34
35 return s
36
37end
38
O(n)
, as we iterate over the string with multiple pointers but only do one iteration of each pointer.O(1)
Given an array of integers, transform the array in-place to a max heap.
Given an array of integers, return an array of triplets such that i != j != k and nums[i] + nums[j] + nums[k] = 0.
Given the head of a linked list, reverse the list and return the new head.
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.
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.