Reverse Strings with Python
QA/SDET Interview Questions— 6 LeetCode Solutions
What’s the easiest way to reverse a string in Python? Well, it’s just a 2-liner!
def reverse_string(s):
return s[::-1]
ChatGPT offers a few additional easy solutions:
As automation QA who author tests, we may be asked to test string reversal with a test framework, PyTest for example:
We can theoretically call the split() function to split the string into words, reverse the words with reverse() or reversed(), then join the words with a space character in between. But an interviewer might (subjectively) consider this cheating, when we’re using a bunch of helper methods and not tackling the essence of the problem. But who knows? If it’s okay with your interviewer, go ahead and proceed this way.
For the situations when we aren’t allowed to use in-built helper methods, let’s take a tour of the LeetCode problems pertinent to string reversal:
It’d be logical to for us start with the Easy difficulty level and then move onto the Medium one.
1. LeetCode 344 — Reverse String — Easy
Solutions
Let’s consider an answer, where the entire logic for reversing a string is based on using the opposite directional 2-pointer approach:
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
left, right = 0, len(s) - 1
while left < right:
s[left], s [right] = s[right], s[left]
left, right = left + 1, right - 1
# Test the function
solution = Solution()
print(solution.reverseString(["h","e","l","l","o"]))
print(solution.reverseString(["H","a","n","n","a","h"]))
# Time: O(n) - Linear
# Space: O(1) - Constant
In case an interviewer wants to see additional solutions, those are captioned below.
💡 Hint: Use a stack data structure, but know that it takes extra space.
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
stack = []
for c in s:
stack.append(c)
i = 0
while stack:
s[i] = stack.pop()
i += 1
# Time: O(n) - Linear
# Space: O(n) - Linear - Stack
💡 Hint: Use recursion, but know that it takes extra space on the call stack.
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
def reverse(left, right):
if left < right:
s[left], s[right] = s[right], s[left]
reverse(left + 1, right - 1)
reverse(0, len(s) -
# Time: O(n) - Linear
# Space: O(n) - Linear - Recursion
2. LeetCode 541. Reverse String II — Easy
Solutions
class Solution:
def reverseStr(self, s: str, k: int) -> str:
a = list(s)
for i in range(0, len(a), 2*k):
a[i : i + k] = reversed(a[i : i + k])
return "".join(a)
# Test the function
solution = Solution()
print(solution.reverseStr("abcdefg", 2)
print(solution.reverseStr("abcd", 2)
# Time: O(N) - Linear - where N is the size of s. We build a helper array, plus reverse about half the characters in s.
# Space: O(N) - Linear
Below we have an alternative solution without the join() method:
class Solution:
def reverseStr(self, s: str, k: int) -> str:
reverse = True
result = ""
for i in range(0, len(s), k):
sub = s[i : i + k]
if reverse:
result += sub[::-1]
else:
result += sub
reverse = not reverse
return result
If this problem looks like a mind-bender, you are not alone — there are lots of folks complaining about it. Thankfully, one kind user has rephrased the problem for us:
3. LeetCode 557. Reverse Words in a String III— Easy
Solutions
Frankly, there are fast solutions which the built-in methods yield, like the one below:
class Solution:
def reverseWords(self, s: str) -> str:
slist = s.split(' ')
rev = []
for i in slist:
w = i[::-1]
rev.append(w)
return " ".join(rev)
Again, if such approach satisfies the conditions of your interview, please proceed with it. If not, here’s how we solve it with 2 pointers:
class Solution:
def reverseWords(self, s: str) -> str:
s = list(s)
l = 0
for r in range(len(s)):
if s[r] == " " or r == len(s) - 1:
temp_l, temp_r = l, r - 1
if r == len(s) - 1:
temp_r = r
while temp_l < temp_r:
s[temp_l], s[temp_r] = s[temp_r], s[temp_l]
temp_l += 1
temp_r -= 1
l = r + 1
return "".join(s)
# Test the function
solution = Solution()
print(solution.reverseWords("Let's take LeetCode contest")
print(solution.reverseWords("Mr Ding")
# Time: O(n) - Linear - where n is the size of s.
# Space: O(1) - Constant
# If we're converting s to a list, technically we are using extra memory O(n). But generally we don't count the output as memory. The list is not necessary; but if we don't use the list, we still end up having to use extra memory by the string manipulation (by taking substrings and then manipulating the entire string). Depending on how you see it, technically we're using extra memory. If you or your interviewer don't consider it a constraint, then space efficiency is O(1) - Constant.
4. LeetCode 345. Reverse Vowels of a String - Easy
Solutions
class Solution:
def reverseVowels(self, s: str) -> str:
vowels = "aeiouAEIOU"
slist = list(s)
i, j = 0, len(slist) - 1
while (i < j):
if slist[i] not in vowels:
i += 1
continue
if slist[j] not in vowels:
j -= 1
continue
slist[i], slist[j] = slist[j], slist[i]
i += 1
j -= 1
return "".join(slist)
# Test the function
solution = Solution()
print(solution.reverseVowels("hello")
print(solution.reverseVowels("leetcode")
# Time: O(n) - Linear - where n is the length of the input string s. The two pointers i and j move towards each other, and each character is processed once.
# Space: O(n) - Linear - because we create a list to store the characters of the input string. The space used is proportional to the length of the input string. Other than that, we use a constant amount of extra space for the vowels string and a few integer variables, which doesn't depend on the input size.
You may also like a variant with a temporary variable:
class Solution:
def reverseVowels(self, s: str) -> str:
vowels = 'aeiouAEIOU'
slist = list(s)
l, r = 0, len(slist) - 1
while l < r:
while l < r and slist[l] not in vowels:
l += 1
while l < r and slist[r] not in vowels:
r -= 1
tmp = slist[l]
slist[l] = slist[r]
slist[r] = tmp
l += 1
r -= 1
return "".join(slist)
# Test the function
solution = Solution()
print(solution.reverseVowels("hello")
print(solution.reverseVowels("leetcode")
Or, perhaps, you are a fan of a queue data structure:
class Solution:
def reverseVowels(self, s: str) -> str:
vs = set("aeiouAEIOU")
v = [c for c in s if c in vs]
res = ""
for c in s:
if c in vs:
res += v.pop()
else:
res += c
return res
5. LeetCode 151. Reverse Words in a String — Medium
Solutions
As usual, a combo of built-in methods makes it all fast and simple:
class Solution:
def reverseWords(self, s: str) -> str:
return " ".join(reversed(s.split()))
And even if we ditch the split(), we still have to handle the reversal function:
class Solution:
def trim_spaces(self, s: str) -> list:
left, right = 0, len(s) - 1
while left <= right and s[left] == ' ':
left += 1
while left <= right and s[right] == ' ':
right -= 1
output = []
while left <= right:
if s[left] != ' ':
output.append(s[left])
elif output[-1] != ' ':
output.append(s[left])
left += 1
return output
def reverse(self, l: list, left: int, right: int) -> None:
while left < right:
l[left], l[right] = l[right], l[left]
left, right = left + 1, right - 1
def reverse_each_word(self, l: list) -> None:
n = len(l)
start = end = 0
while start < n:
while end < n and l[end] != ' ':
end += 1
self.reverse(l, start, end - 1)
start = end + 1
end += 1
def reverseWords(self, s: str) -> str:
l = self.trim_spaces(s)
self.reverse(l, 0, len(l) - 1)
self.reverse_each_word(l)
return ''.join(l)
# Test the function
solution = Solution()
print(solution.reverseWords("the sky is blue")
print(solution.reverseWords(" hello world ")
print(solution.reverseWords("a good example")
# Time: O(n) - Linear
# Space: O(n) - Linear
To avoid the built-in reverse() function entirely, there’s another solution we can use:
class Solution:
def reverseOneWord(self, s: list, debut: int, fin: int):
i = debut
j = fin
while i < j:
s[i], s[j] = s[j], s[i]
i += 1
j -= 1
def deleteSpacesSeries(self, s: list):
i = len(s)-1
while i >= 0 and s[i].isspace():
s.pop()
i -= 1
i = 0
while i < len(s) and s[i].isspace():
i += 1
write_i = 0
while i < len(s):
if not (s[i - 1].isspace() and s[i].isspace()):
s[write_i] = s[i]
write_i += 1
i += 1
for _ in range(len(s) - write_i):
s.pop()
def reverseWords(self, s: str) -> str:
s = list(s)
self.reverseOneWord(s, 0, len(s) - 1)
i = 0
motDebut = 0
motFin = 0
estMotFini = False
while i < len(s):
if s[i].isspace():
if estMotFini:
self.reverseOneWord(s, motDebut, motFin)
estMotFini = False
elif not estMotFini:
estMotFini = True
motDebut = i
motFin = i
else:
motFin += 1
i+=1
if estMotFini:
self.reverseOneWord(s, motDebut, motFin)
self.deleteSpacesSeries(s)
return "".join(s)
6. LeetCode 186. Reverse Words in a String II - Medium
Solutions
Here’s one solution with linear time and space complexity:
class Solution:
def reverseWords(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
def in_place_reverse(s, start, end):
left, right = start, end
while left < right:
s[left], s[right] = s[right], s[left]
left, right = left + 1, right -1
in_place_reverse(s, 0, len(s)-1)
i = j = 0
while j <= len(s):
if j == len(s) or s[j] == " ":
in_place_reverse(s, i, j - 1)
i = j + 1
j += 1
# Test the function
solution = Solution()
print(solution.reverseWords(["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"])
print(solution.reverseWords(["a"])
# Time: O(n) - Linear
# Space: O(n) - Linear
Here’s another take on that solution:
class Solution:
def reverseWords(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
def reverse_words_helper(left, right):
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
reverse_words_helper(0, len(s) - 1)
left = 0
for index, char in enumerate(s):
if char == " ":
reverse_words_helper(left, index - 1)
left = index + 1
reverse_words_helper(left, len(s) - 1)
Resources:
- GitHub Repo with Solution Code: https://github.com/lana-20/reverse-string-python-algo/
- Big O Cheat Sheet: https://www.bigocheatsheet.com/
- Big O Notation and Time Complexity — Easily Explained: https://www.happycoders.eu/algorithms/big-o-notation-time-complexity/
Happy coding and debugging!
I welcome any comments and contributions to the subject. Connect with me on LinkedIn, X , GitHub, or IG.