Jaspreet singh

Posted on Jun 29

Reverse every word in a string

#java #algorithms #interview #programming

leetcode.com

Problem Statement

Given a string s, reverse the order of the words.

A word is defined as a sequence of non-space characters.

The returned string should:

Remove leading spaces.
Remove trailing spaces.
Reduce multiple spaces between words to a single space.

Brute Force Intuition

In an interview, you can explain it like this:

Split the string into individual words, reverse their order, and join them back with a single space.

Although simple, this creates an extra array of words.

Complexity

Time Complexity: O(N)
Space Complexity: O(N)

Brute Force Code

class Solution {

    public String reverseWords(String s) {

        String[] words = s.trim().split("\\s+");

        StringBuilder sb = new StringBuilder();

        for (int i = words.length - 1; i >= 0; i--) {

            sb.append(words[i]);

            if (i != 0)
                sb.append(" ");
        }

        return sb.toString();
    }
}

Moving Towards the Optimal Approach

Instead of storing every word separately,

we can traverse the string from the end.

Whenever we find a complete word,

append it directly to the answer.

This naturally reverses the word order.

Pattern Recognition

Whenever you see:

Reverse Words
Ignore Extra Spaces
Process String Efficiently

Think:

Two Pointers + Reverse Traversal

Key Observation

Traverse the string:

Right → Left

Skip spaces.

Extract one word.

Append it.

Repeat until the beginning.

Optimal Java Solution

class Solution {

    public String reverseWords(String s) {

        StringBuilder ans = new StringBuilder();

        int i = s.length() - 1;

        while (i >= 0) {

            while (i >= 0 && s.charAt(i) == ' ')
                i--;

            if (i < 0)
                break;

            int j = i;

            while (j >= 0 && s.charAt(j) != ' ')
                j--;

            ans.append(s.substring(j + 1, i + 1));

            ans.append(" ");

            i = j;
        }

        return ans.toString().trim();
    }
}

Dry Run

Input

"  hello   world  "

Skip trailing spaces.

Extract:

world

Append.

Continue.

Extract:

hello

Final Output:

"world hello"

Why This Works?

By traversing from right to left,

words are collected in reverse order automatically.

Extra spaces are skipped during traversal,

and trim() removes the final extra space.

Complexity Analysis

Metric	Complexity
Time Complexity	O(N)
Space Complexity	O(N)

Interview One-Liner

Traverse the string from right to left, extract one word at a time, and append it to the answer while skipping extra spaces.

Pattern Learned

Reverse Order

+

Skip Extra Spaces

↓

Two Pointer Traversal

Memory Trick

Think:

Start From End

↓

Skip Spaces

↓

Extract Word

↓

Append

↓

Repeat

Mental Model

Right to Left

↓

Collect Words

↓

Build Answer

Whenever you hear:

"Reverse the order of words"

your brain should immediately think:

Traverse from Right + Two Pointers

DEV Community