Introduction

Reversing a string in true O(1) runtime is not possible when you must produce an actual reversed copy. Any real reversal must touch characters, so runtime grows with input length. The practical target is O(n) time with predictable memory behavior, or an O(1) view object when lazily indexing original data.

Why Full Reversal Cannot Be O(1)

A string of length n contains n positions that may need to move. If output must contain all characters in reverse order, each character must be read and written at least once. That gives a lower bound of linear work.

In short:

• Reading all characters requires O(n)
• Writing reversed output requires O(n)
• Therefore full materialization cannot be constant time

Efficient In-Place Style on Mutable Buffers

If your language supports mutable arrays, a two-pointer swap loop is optimal in practice.

1def reverse_chars(chars: list[str]) -> None:
2    left, right = 0, len(chars) - 1
3    while left < right:
4        chars[left], chars[right] = chars[right], chars[left]
5        left += 1
6        right -= 1
7
8buf = list("codemia")
9reverse_chars(buf)
10print("".join(buf))  # aimedoc

Complexity is O(n) time and O(1) extra space.

Immutable String Languages

When strings are immutable, create a new reversed string. Python slicing is concise and implemented efficiently in C.

1def reverse_string(s: str) -> str:
2    return s[::-1]
3
4print(reverse_string("algorithm"))

This is still O(n) time and O(n) memory for the new string.

C++ Example with Standard Library

std::reverse is a reliable option for mutable character containers.

1#include <algorithm>
2#include <iostream>
3#include <string>
4
5int main() {
6    std::string s = "runtime";
7    std::reverse(s.begin(), s.end());
8    std::cout << s << "\n";
9    return 0;
10}

The algorithm is linear and highly optimized by standard library implementations.

The O(1) Case People Usually Mean

You can create a lightweight reversed view in O(1) time by storing original data and remapping indexes. This does not materialize a new string immediately.

1class ReversedView:
2    def __init__(self, text: str):
3        self._text = text
4
5    def __len__(self) -> int:
6        return len(self._text)
7
8    def __getitem__(self, i: int) -> str:
9        if i < 0 or i >= len(self._text):
10            raise IndexError("index out of range")
11        return self._text[len(self._text) - 1 - i]
12
13view = ReversedView("network")
14print(view[0])  # k
15print(view[1])  # r

Constructing ReversedView is O(1), but iterating across all characters is still O(n) total.

Choosing the Right Approach

Pick by requirement:

• Need actual reversed string now: do standard linear reversal
• Need only occasional reverse-index access: use a view abstraction
• Need minimal allocations on large data: mutate buffers in place when possible

The best solution depends on output contract, not on forcing O(1) where it cannot apply.

Interview Friendly Explanation

If this question comes up in an interview, answer in two parts. First, state clearly that full reversal is linear because every character must be processed. Second, mention that O(1) construction is possible only for a lazy reverse view that defers work until access time. This shows you understand both asymptotic limits and practical design tradeoffs.

Common Pitfalls

• Claiming O(1) for algorithms that still read all characters
• Ignoring immutability costs in languages that allocate new strings
• Benchmarking tiny inputs and drawing wrong complexity conclusions
• Forgetting Unicode grapheme boundaries in human-language text reversal
• Optimizing for asymptotic notation while ignoring real memory behavior

Correct complexity analysis prevents misleading performance expectations.

Summary

• Full string reversal cannot be true O(1) in general.
• Materialized reversal requires linear work in input length.
• In-place swaps give O(n) time with constant extra memory on mutable buffers.
• Immutable strings require new allocation for reversed output.
• O(1) creation is possible only for lazy reversed views, not full output.