Skip to content

Volume ITechnology

4.0.11 — Reverse a String, and Reverse the Words ​

Classic · Easy · LeetCode 344 (Reverse String), LeetCode 151 (Reverse Words in a String), LeetCode 557 (Reverse Words III)

The problem ​

  1. Reverse a string. "hello" becomes "olleh".
  2. Reverse the order of the words. "the sky is blue" becomes "blue is sky the".
  3. Reverse each word but keep the word order. "the sky is blue" becomes "eht yks si eulb".

The interviewer usually adds: "without slicing", or "without built-in functions", or "in place".

1. Reverse a string ​

The Python answer ​

python
s = "hello"
print(s[::-1])               # → olleh
print("".join(reversed(s)))  # → olleh

s[::-1] is a slice. The three slots are start, stop and step. Leaving start and stop empty means "the whole string". A step of -1 means "walk backwards". So it reads the string from the last character to the first.

reversed(s) gives the characters from last to first, one at a time. "".join(...) glues them into one string with nothing between them.

Say both. Then the interviewer will ask for it by hand.

By hand, with two indexes ​

Here is a fact that shapes this whole problem. Python strings cannot be changed. s[0] = "H" raises a TypeError. A string is immutable: once made, it stays as it is. Every "change" really builds a new string.

Why did Python's designers do this? An unchangeable string can be shared safely. If two variables point to the same string, neither can surprise the other by editing it. It can also be used as a dictionary key, because its value, and so its hash, can never change. Chapter 4.3 explains why a key that changes would break a dictionary.

So to reverse "in place", first turn the string into a list of characters. A list can be changed. Then use Move 4 from 4.0.0, the two indexes walking inward.

python
def reverse_string(s: str) -> str:
    chars = list(s)                       # (1)
    left, right = 0, len(chars) - 1
    while left < right:                   # (2)
        chars[left], chars[right] = chars[right], chars[left]   # (3)
        left += 1
        right -= 1
    return "".join(chars)                 # (4)

print(reverse_string("hello"))   # → olleh
print(reverse_string("ab"))      # → ba
print(repr(reverse_string("")))  # → ''

(1) Copy the characters into a list that we are allowed to change.

(2) Stop when the indexes meet. For an odd length, the middle character stays where it is.

(3) Swap the outer pair.

(4) Glue the list back into a string.

LeetCode 344 gives you the list directly and asks you to change it in place. Then you skip steps (1) and (4), and the extra memory really is O(1).

Two answers that look fine but are slow or fragile ​

Adding characters one at a time.

python
def reverse_concat(s: str) -> str:
    out = ""
    for ch in s:
        out = ch + out     # puts each new character at the front
    return out

print(reverse_concat("hello"))   # → olleh

It is correct. But each ch + out builds a brand-new string and copies everything in out into it. The copies get longer every time: 1 character, then 2, then 3, up to n. The total is 1 + 2 + \dots + n, about \frac{n^2}{2} copies. That is O(n^2). For a million characters it is about 500 billion character copies. Collecting pieces in a list and joining once at the end is O(n).

Recursion.

python
def reverse_rec(s: str) -> str:
    if len(s) <= 1:
        return s
    return reverse_rec(s[1:]) + s[0]

print(reverse_rec("hello"))   # → olleh

It is a nice idea: reverse everything after the first character, then put the first character at the end. But each s[1:] copies almost the whole string, so it is O(n^2) again. It also makes one call per character, so a string of 2,000 characters hits Python's recursion limit.

2. Reverse the order of the words ​

The Python answer ​

python
def reverse_words(s: str) -> str:
    return " ".join(reversed(s.split()))     # (1)

print(reverse_words("the sky is blue"))     # → blue is sky the
print(reverse_words("  hello   world  "))   # → world hello

(1) s.split() with no argument splits on any run of spaces and throws away spaces at the ends. So " hello world " becomes ["hello", "world"]. Reverse that list, then join with single spaces.

Common mistake. s.split(" ") with a space argument behaves differently. It splits at every single space, so runs of spaces produce empty strings: "a b".split(" ") gives ['a', '', 'b']. LeetCode 151 wants single spaces in the answer, so use split() with no argument.

By hand, without split ​

Walk the string from the end. Skip spaces. When you find the end of a word, walk back to its start and collect it.

python
def reverse_words_manual(s: str) -> str:
    words = []
    i = len(s) - 1
    while i >= 0:
        while i >= 0 and s[i] == " ":      # (1)
            i -= 1
        if i < 0:
            break
        end = i                            # (2)
        while i >= 0 and s[i] != " ":      # (3)
            i -= 1
        words.append(s[i + 1:end + 1])     # (4)
    return " ".join(words)

print(reverse_words_manual("  the sky   is blue "))   # → blue is sky the

(1) Skip any spaces.

(2) i is now on the last letter of a word. Remember it.

(3) Move left until a space, or the start of the string.

(4) The word runs from just after that space to end. Words are found from the last to the first, so they are already in reversed order.

The in-place trick: reverse twice ​

In languages where strings can be changed, the interviewer may ask for this with O(1) extra memory. Here is the trick. Reverse the whole string, then reverse each word on its own.

the sky is blue
eulb si yks eht      ← whole string reversed: words are in the right order, but each is backwards
blue is sky the      ← each word reversed back

Reversing the whole string puts the words in the right order but spells each one backwards. Reversing each word fixes the spelling and leaves the order alone.

python
def reverse_range(chars: list[str], i: int, j: int) -> None:
    while i < j:
        chars[i], chars[j] = chars[j], chars[i]
        i += 1
        j -= 1

def reverse_words_inplace(s: str) -> str:
    chars = list(s)
    reverse_range(chars, 0, len(chars) - 1)          # (1)
    start = 0
    for end in range(len(chars) + 1):
        if end == len(chars) or chars[end] == " ":   # (2)
            reverse_range(chars, start, end - 1)     # (3)
            start = end + 1
    return "".join(chars)

print(reverse_words_inplace("the sky is blue"))   # → blue is sky the

(1) Reverse everything.

(2) A word ends at a space, or at the end of the string.

(3) Reverse just that word back.

This version assumes single spaces between words. With extra spaces, you would first squeeze them out, using the write-pointer move from 4.0.18. The same reverse-twice idea rotates an array in 4.0.17.

3. Reverse each word, keep the order ​

python
def reverse_each_word(s: str) -> str:
    return " ".join(word[::-1] for word in s.split(" "))   # (1)

print(reverse_each_word("the sky is blue"))   # → eht yks si eulb

(1) Here split(" ") is the right choice. LeetCode 557 promises single spaces, and splitting on exactly one space keeps any spacing the same.

Counting words falls out of the same tools: len(s.split()).

Complexity ​

Every correct version above is O(n) time, where n is the length of the string. The two-index version uses O(1) extra memory when it is given a list. With a Python string, it needs an O(n) list, because the string itself cannot be changed. The character-by-character ch + out and the recursive version are O(n^2).

What the interviewer will push on ​

These are the questions that usually come right after you solve it. Each one has a short, plain answer you can say out loud.

"Reverse the string in place." Python strings cannot be changed. So turn the string into a list, reverse the list with two indexes, and join it back. Say that this uses O(n) extra memory for the list, because of how Python strings work.

"What is wrong with out = ch + out inside a loop?" Each step builds a whole new string and copies everything built so far. The copies get longer every time. So the total work is O(n^2).

"Reverse the words using almost no extra memory." Reverse the whole string first. The words are now in the right order, but each word is spelled backwards. Then reverse each word on its own to fix the spelling.

"What if there are several spaces between words?" Use s.split() with no argument. It splits on any run of spaces and drops spaces at the ends. s.split(" ") would give empty strings for the extra spaces.

One thing to volunteer: "The same reverse-twice trick rotates an array in place."

Next: 4.0.12 String Basics. Palindromes, counting vowels, character frequency, and cleaning up a messy string.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet