Strings

The problem

You're writing the "undo" feature for a text editor, and a tiny sub-task lands on your desk: reverse the word the user just typed. It sounds trivial — "racecar" becomes "racecar", "hello" becomes "olleh". Then a colleague pastes in a 10-megabyte log file and your neat little function takes seconds to run. On one string.

How can flipping some characters be slow? The answer is hiding in what a string actually is underneath — and once you see it, the fix is obvious.

A first attempt

The natural instinct is to build the answer one character at a time, front to back:

def reverse(s):
    result = ""
    for ch in s:
        result = ch + result   # prepend each character
    return result

In most languages a string is immutable — you can't change it in place. So ch + result doesn't tweak result; it allocates a brand-new string and copies every character over. Do that n times and you've copied 1 + 2 + 3 + … + n characters — that's O(n²). For a 10 MB string, quadratic is exactly why your editor froze.

The insight

A string is just an array of characters. The reason we can't edit it in place is a language choice, not a law of nature. So copy the characters into a real, mutable array once, do all your work there with cheap in-place swaps, then build the final string once at the end.

That turns the whole job into a single two-pointer pass: one index walking in from the left, one from the right, swapping as they meet.

How it works

"hello"  ->  h  e  l  l  o
             i           j     swap h,o
             o  e  l  l  h
                i     j        swap e,l
             o  l  l  e  h
                   ij          pointers meet — done
result: "olleh"

The code

def reverse(s):
    chars = list(s)                 # strings are immutable — work on a list
    i, j = 0, len(chars) - 1
    while i < j:
        chars[i], chars[j] = chars[j], chars[i]
        i += 1
        j -= 1
    return "".join(chars)           # build the final string once

function reverse(s: string): string {
  const chars = s.split("");
  let i = 0, j = chars.length - 1;
  while (i < j) {
    [chars[i], chars[j]] = [chars[j], chars[i]];
    i++;
    j--;
  }
  return chars.join("");
}

String reverse(String s) {
    char[] chars = s.toCharArray();
    int i = 0, j = chars.length - 1;
    while (i < j) {
        char tmp = chars[i];
        chars[i] = chars[j];
        chars[j] = tmp;
        i++;
        j--;
    }
    return new String(chars);
}

#include <string.h>

/* C strings are already mutable char arrays — reverse in place. */
void reverse(char *s) {
    int i = 0, j = (int)strlen(s) - 1;
    while (i < j) {
        char tmp = s[i];
        s[i] = s[j];
        s[j] = tmp;
        i++;
        j--;
    }
}

#include <string>
using namespace std;

string reverse_str(string s) {   // std::string is mutable; take a copy
    int i = 0, j = (int)s.size() - 1;
    while (i < j) {
        swap(s[i], s[j]);
        i++;
        j--;
    }
    return s;
}

Complexity

Compare that to the O(n²) naive version. Same output, but the 10 MB string now finishes in a blink.

When to use it

Practice

Recap

• A string is an array of characters; the only thing stopping in-place edits is immutability, a language choice.
• Because immutable strings copy on every change, building them character-by-character in a loop is O(n²) — collect in a mutable buffer and join once.
• Reversing, palindrome checks, and most string work reduce to array techniques like the two-pointer sweep.