Reverse a String
Write a Python function that takes a string s as input and returns the string reversed.
Examples:
Example 1:
Input: s = "hello"
Output: "olleh"
Example 2:
Input: s = "Python"
Output: "nohtyP"
Constraints:
0 <= len(s) <= 5 * 104sconsists of printable ASCII characters.
Function Signature (Python):
class Solution:
def reverseString(self, s: str) -> str:
# Your code here
pass
Related Python Concepts
join() method reversed() built-in Time Complexity Space ComplexityHint
For an interview, think about how you would reverse a sequence of items if you couldn't use a special shortcut. Consider:
- Swapping Elements: If you had a mutable sequence (like a list of characters), how could you swap elements from the ends moving inwards?
- Building Anew: How can you construct a new sequence by taking elements from the original in reverse order?
- String Properties: Remember that strings are immutable in Python. How does this affect your approach if you want to modify characters?
Solution Explanation & Interview Strategy
The Goal: Turn a string like "HELLO" into "OLLEH".
In a data science or software interview, the interviewer wants to see not just that you can solve it, but how you think about the problem, your understanding of fundamental operations, and efficiency. Simply using a built-in Python shortcut might be too quick and hide your problem-solving process!
Let's explore approaches, starting with those that better demonstrate core concepts, as these are often preferred in interviews.
Approach 1: Two-Pointer Technique (Often Preferred in Interviews)
This is a classic algorithmic pattern for in-place reversal. However, strings are immutable in Python (they cannot be changed directly after creation). So, to use a two-pointer swapping technique, we must first convert the string to a list of characters (which is mutable). We then perform the in-place reversal on the list and finally join the list back into a string.
class Solution:
def reverseString_two_pointer(self, s: str) -> str:
if not s:
return ""
char_list = list(s) # Convert string to list of characters (mutable)
left, right = 0, len(char_list) - 1
while left < right:
# Swap characters
char_list[left], char_list[right] = char_list[right], char_list[left]
# Move pointers inward
left += 1
right -= 1
return "".join(char_list) # Convert list back to string
# Example Usage:
# sol = Solution()
# print(sol.reverseString_two_pointer("hello")) # Output: olleh
char_listbecomes['h', 'e', 'l', 'l', 'o'].left = 0,right = 4.- Swap
char_list[0]('h') andchar_list[4]('o'). List:['o', 'e', 'l', 'l', 'h'].left = 1,right = 3. - Swap
char_list[1]('e') andchar_list[3]('l'). List:['o', 'l', 'l', 'e', 'h'].left = 2,right = 2. left(2) is not less thanright(2). Loop terminates."".join(['o', 'l', 'l', 'e', 'h'])returns "olleh".
Complexity Analysis:
Time Complexity: O(N). Converting string to list is O(N). The while loop runs N/2 times (O(N) swaps). Joining list to string is O(N). Total: O(N) + O(N) + O(N) = O(N).
Space Complexity: O(N) to store char_list. The swaps are in-place on the list, but the list itself is new storage.
Approach 2: Iterative Construction (Character by Character Prepend)
This approach involves iterating through the input string and prepending each character to a new string. While conceptually simple, it's important to discuss its efficiency implications in Python.
class Solution:
def reverseString_iterative_prepend(self, s: str) -> str:
reversed_s = ""
for char in s:
reversed_s = char + reversed_s # Prepend character
return reversed_s
reversed_sis"".char= 'c'.reversed_sbecomes 'c' + "" = "c".char= 'a'.reversed_sbecomes 'a' + "c" = "ac".char= 't'.reversed_sbecomes 't' + "ac" = "tac".- Returns "tac".
Complexity Analysis:
Time Complexity: O(N2) in Python. String concatenation (char + reversed_s) creates a new string in each iteration by copying all characters from both operands. If reversed_s has length k, this takes O(k) time. This happens N times, with k growing from 0 to N-1. The total is roughly 1 + 2 + ... + N-1 operations, which is O(N2).
Space Complexity: O(N) for the final reversed_s. (Technically, intermediate strings are also created, but the dominant factor for final storage is O(N)).
Note for Interviews: Highlighting the O(N2) nature of repeated string concatenation in Python is a good discussion point.
Approach 3: Iterative Construction with a List (More Efficient Manual Build)
To avoid the O(N2) time complexity of string concatenation, we can build a list of characters and then join them. Appending to a list is an O(1) operation on average.
class Solution:
def reverseString_list_build(self, s: str) -> str:
char_list = []
for char in s:
char_list.insert(0, char) # Insert at the beginning (O(N) per insert)
# A more efficient way would be: char_list.append(char) and then char_list.reverse()
return "".join(char_list)
# More efficient list building:
def reverseString_list_build_optimized(self, s: str) -> str:
char_list = []
for char in s:
char_list.append(char) # O(1) on average
# char_list is now ['h','e','l','l','o']
char_list.reverse() # O(N) in-place reverse
# char_list is now ['o','l','l','e','h']
return "".join(char_list) # O(N)
char_listis[].- Append 'c':
char_listis['c']. - Append 'a':
char_listis['c', 'a']. - Append 't':
char_listis['c', 'a', 't']. char_list.reverse():char_listbecomes['t', 'a', 'c']."".join(char_list)returns "tac".
Complexity Analysis (for reverseString_list_build_optimized):
Time Complexity: O(N). Appending N characters is N * O(1) = O(N). list.reverse() is O(N). join() is O(N). Total: O(N).
Space Complexity: O(N) for char_list.
Note: Using list.insert(0, char) in a loop would lead to O(N2) time complexity because each insertion at the beginning of a list takes O(N) time.
Approach 4: Pythonic Built-in Methods (Concise & Efficient)
Python offers very idiomatic and efficient ways to achieve string reversal. While these are excellent for production code, it's good to demonstrate manual methods first in an interview to showcase fundamental understanding, and then mention these as more concise alternatives.
4a. Using Slicing [::-1]
This is the most common and Pythonic way to reverse a string (or any sequence).
class Solution:
def reverseString_slicing(self, s: str) -> str:
return s[::-1]
s[::-1]:
- This is extended slice syntax:
[start:stop:step]. - Omitting
startandstopdefaults to the entire string. - A
stepof-1means iterate backwards.
Complexity Analysis:
Time Complexity: O(N). Slicing creates a new reversed string by iterating through the original once.
Space Complexity: O(N). A new string of length N is created.
4b. Using reversed() and join()
The reversed() built-in function returns a reverse iterator, which can then be joined to form a string.
class Solution:
def reverseString_reversed_join(self, s: str) -> str:
return "".join(reversed(s))
reversed(s): Creates an iterator that yields characters of 's' in reverse order."".join(...): Concatenates all items from the iterator into a new string.
Complexity Analysis:
Time Complexity: O(N). reversed() is efficient, and join() iterates N times.
Space Complexity: O(N) for the new string created by join(). The iterator itself is O(1).
Interview Context for Built-ins: While s[::-1] and "".join(reversed(s)) are excellent, idiomatic Python for this task, interviewers often want to see if you can implement the logic manually (like with two pointers or iterative list building) first This demonstrates your understanding of core algorithms and data manipulation. After showing a manual approach, you can then mention these Pythonic solutions as more concise alternatives.
Key Takeaways for Interviews:
- Start with fundamentals: The two-pointer approach on a list (due to string immutability) is a strong starting point to showcase algorithmic thinking.
- Discuss trade-offs: Explain why direct string concatenation (Approach 2) is inefficient (O(N2)) and how using a list to build the result (Approach 3, optimized version) improves this to O(N).
- Mention Pythonic solutions: After demonstrating a manual approach, show your knowledge of Python's elegant shortcuts (slicing,
reversed()) and their efficiency. - Always consider immutability: Remember that strings are immutable in Python, so any "reversal" will create a new string. This is a key point to articulate.