Reverse a String

Q: What is the time complexity of reversing a string?

Reversing takes O(n) time, because every character has to move to a new position and each one is handled once. Building a new string costs O(n) extra space. Swapping with two pointers needs only O(1) extra space when the characters are already in a mutable array.

Q: How do you reverse a string without a built-in reverse function?

Copy the characters into an array, place one pointer at each end, swap the two characters, and move the pointers toward each other until they meet. Alternatively, loop from the last index down to the first and append each character to a builder. Both produce the reversed string in one pass.

Q: Can you reverse a string in place?

Only when the characters live in a mutable buffer, such as a char array in C, Java or C#, a list in Python, or a std::string in C++. Strings in Java, Python, JavaScript and many other languages are immutable, so you copy them into an array, swap inside it, and build a new string. The swapping step itself is in place either way.

Q: Why does the two pointer loop stop at the middle?

Each swap places two characters in their final positions, so after n / 2 swaps every character is where it belongs. Continuing past the middle swaps the same pairs back and undoes the work. When the length is odd, the middle character already sits at its own mirror index and needs no swap.

BeginnerArrays and strings Two pointers

+10

You get a string s made of English letters and digits. Return a new string with the same characters in reverse order, so the last character comes first and the first comes last. Keep every character exactly as it is, including its case.

Function

reverseString(s: string) → string

sstring: the string to reverse
Returnsstring: the characters of s in reverse order

Constraints

1 ≤ s.length ≤ 10⁴
s contains only English letters (a to z, A to Z) and digits (0 to 9).

Examples

Input: s = "Coddy2026"
Output: "6202yddoC"
Explanation: Read Coddy2026 from its last character to its first: 6, 2, 0, 2, then y, d, d, o and finally the capital C.

Input: s = "noon"
Output: "noon"
Explanation: noon is a palindrome, so its reverse is the same word. The outer ns trade places, then the two os do.

+14 hidden tests on Submit

Follow-up

How would you reverse the order of the words in a sentence, turning hello big world into world big hello, while every word keeps its letters in order?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Every character has a fixed destination: the one at index i belongs at index n-1-i. You can write the characters into a new string in that order, or swap them in pairs from both ends. The swap is the version interviewers ask for, because the same two pointer move reverses an array in place and checks a palindrome.

Copy the characters from the back

Intuition

The reverse of s starts with the last character of s, continues with the second to last, and ends with the first. So walk an index from n-1 down to 0 and append each character to the answer as you meet it. For Coddy2026 you append 6, 2, 0, 2, y and so on, which spells 6202yddoC.

Each character is read once and written once, so the work is O(n). The answer is a second string of n characters, which is O(n) extra space.

How you append matters. Adding one character to an immutable string with + copies the whole string each time, and for n = 10^4 that is about 5 × 10^7 character copies. Collect the characters in a list or a string builder and join them once at the end.

Algorithm

Create an empty list or string builder for the answer.
Loop i from n-1 down to 0.
Append s[i] to the answer.
Join the answer into a string and return it.

def reverseString(s):
    result = []
    for i in range(len(s) - 1, -1, -1):
        result.append(s[i])
    return "".join(result)

Swap from both ends with two pointers

Intuition

Reversing pairs up the characters from the outside in. The first and the last trade places, then the second and the second to last, and so on toward the middle. Put a pointer left on index 0 and a pointer right on index n-1, swap the two characters, and move both pointers one step inward.

Stop when the pointers meet or cross. In noon the pointers start on 0 and 3, then move to 1 and 2, and then cross, after two swaps. With an odd length such as xYz they meet on the middle character, which already sits in its final place, so it is never touched. Every swap puts two characters in their final spots, so n / 2 swaps finish the job.

The swaps themselves need only one temporary variable, O(1) extra space. Most languages do not let you change a string in place, so you first copy it into a character array, which costs O(n). In an interview where the input is already a character array, this approach reverses it with no extra memory at all.

Algorithm

Copy s into an array of characters.
Set left = 0 and right = n-1.
While left < right, swap the characters at left and right, then add 1 to left and subtract 1 from right.
Turn the array back into a string and return it.

def reverseString(s):
    chars = list(s)
    left, right = 0, len(chars) - 1
    while left < right:
        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1
    return "".join(chars)

Pitfalls and edge cases

Reversing looks like one line, and the bugs hide in the loop bounds and in how the answer is built.

Looping left all the way to n-1. Past the middle, every pair is swapped a second time and the string comes back unchanged. Stop at left < right.
Starting the backward loop at n instead of n-1, which reads one position past the end. In Lua and R the indexes run from 1 to n instead.
Building the answer with result = result + ch on an immutable string. Each step copies everything so far, which turns a linear task into a quadratic one on long inputs.
Forgetting the terminating '\0' in C. A buffer of n bytes is one short; allocate n + 1.
Swapping without a temporary variable: after chars[left] = chars[right] the old left character is gone, unless your language swaps both values at once.

Frequently asked questions4

What is the time complexity of reversing a string?

Reversing takes O(n) time, because every character has to move to a new position and each one is handled once. Building a new string costs O(n) extra space. Swapping with two pointers needs only O(1) extra space when the characters are already in a mutable array.

How do you reverse a string without a built-in reverse function?

Copy the characters into an array, place one pointer at each end, swap the two characters, and move the pointers toward each other until they meet. Alternatively, loop from the last index down to the first and append each character to a builder. Both produce the reversed string in one pass.

Can you reverse a string in place?

Only when the characters live in a mutable buffer, such as a char array in C, Java or C#, a list in Python, or a std::string in C++. Strings in Java, Python, JavaScript and many other languages are immutable, so you copy them into an array, swap inside it, and build a new string. The swapping step itself is in place either way.

Why does the two pointer loop stop at the middle?

Each swap places two characters in their final positions, so after n / 2 swaps every character is where it belongs. Continuing past the middle swaps the same pairs back and undoes the work. When the length is odd, the middle character already sits at its own mirror index and needs no swap.

Python

def reverseString(s):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

s = "Coddy2026"

Expected

"6202yddoC"