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 sit 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 and JavaScript are immutable, so you copy them into an array, swap there, and build a new string.

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.

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 starts with the last character and ends with the first, so loop an index from n-1 down to 0 and append each character to the answer. Each character is read once and written once: O(n) time, plus an O(n) answer string.

Append to a list or a string builder and join once at the end. Adding one character to an immutable string with + copies the whole string each time, about 5 × 10^7 character copies for n = 10^4.

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

The first and last characters trade places, then the second and second to last, and so on toward the middle. Put left on index 0 and right on n-1, swap, and step both inward until they meet or cross. Each swap puts two characters in their final places, so n / 2 swaps finish the job. With an odd length such as xYz, the middle character already sits in its place and is never touched.

The swaps need one temporary variable. Most languages cannot change a string in place, so you first copy it into a character array, which costs O(n). When the input is already a mutable array, the reversal uses O(1) extra space.

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

Looping left all the way to n-1. Past the middle every pair is swapped back, 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.
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 questions3

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 sit 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 and JavaScript are immutable, so you copy them into an array, swap there, and build a new string.

def reverseString(s):
    # Write code here
    return s

Test #1

Test #2

Test #3

Argument

s = "Coddy2026"

Expected Output

"6202yddoC"