Skip to main content

Two Pointer

Reverse Words in a String III Solution In C++/Java/Python/JS

Problem Description:

Given a string s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
Illustration of Reverse Words in a String III Problem Description

Examples:

Input: s = "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

Input: s = "Mr Ding"
Output: "rM gniD"

Constraints:

  • 1 <= s.length <= 5 * 104
  • s contains printable ASCII characters.
  • s does not contain any leading or trailing spaces.
  • There is at least one word in s.
  • All the words in s are separated by a single space.

Approach

Intuition:

Let's break down this LeetCode problem step by step. The problem asks us to take a sentence and reverse each individual word while keeping the words in their original positions.

Think of it like flipping each word backwards, but the sentence structure stays the same.

Example: 

If we have the string "This is LearnYard", our result should be "siht si draYnraeL". Notice how each word is reversed individually, but they stay in the same order within the sentence.

The beauty of this problem lies in its simplicity. We need to reverse each word in the string at the exact same place where the word originally exists. 

This means we're not moving words around, we're just rearranging the characters within each word in such a way that the first character now resides at the last. The second character must reside second last and so on. Let's call this a reverse operation.

When we observe this problem carefully, we can see that to maintain the original word order, we can perform the reverse operation on each word one by one as we go through the entire string. This approach ensures that we process each word individually without disturbing the overall sentence structure.

How to find individual words in a string ?

The answer lies in understanding that every word has a clear beginning and end. Each word starts at some specific index in the string and ends at another specific index. 

To deal with this we can use two pointers to locate each word:

First Pointer (Start Finder): This pointer finds where each word begins by skipping over spaces until it hits a non-space character.

Second Pointer (End Finder): Starting from where the first pointer found the word's beginning, this pointer moves forward until it hits a space or reaches the end of the string.

Using these two pointers together, we can identify the exact boundaries of each word efficiently, processing words one by one from left to right.

How to perform the reverse operation?

Once we have identified a word using the two pointer approach, one pointer marksand the other marks the start of the word and the other marking the end.

We can simply reverse that word using a classic two-pointer swapping technique. This is where the magic happens!

The reversal process works like this: We place one pointer at the beginning of the word and another at the end. Then we swap the characters at these two positions. After swapping, we move both pointers closer to each other. The starting pointer moves one step forward, and the ending pointer moves one step backwards. 

We continue this swapping and moving process until the starting pointer becomes greater than the ending pointer. When this condition is met, we know that we've successfully reversed the entire word.

This two pointer approach is extremely efficient because it reverses the word in place without needing extra space, and it guarantees that every character gets swapped exactly once with its corresponding character from the opposite end.

💡
To perform the reverse operation you can use builtin reverse function to reverse each word in a string rather then manually performing the reversal operation.

To know more about this refer here.

Why Avoid using the inbuilt function in an Interview?

While using an inbuilt reverse function is convenient and often the most straightforward approach, it might not be ideal in an interview context for several reasons. Interviewers typically want to see your understanding of basic algorithms and data structures. Implementing the reverse operation manually shows your grasp of fundamental concepts like loops, indexing, and swapping elements. 

Though this method is highly efficient and quick to implement, making it an excellent choice for use in Online Assessments (OAs) and coding contests. 

Why This Approach Works?

This method is particularly elegant because it processes each word independently while maintaining the original sentence structure. We're essentially treating each word as a separate mini-problem, solving it, and then moving on to the next word.

The spaces between words act as natural boundaries that help us identify where one word ends and the next begins.

By using this systematic approach of identifying word boundaries and then reversing each word in place, we can solve this problem efficiently while keeping our code clean and easy to understand.

0:00
/0:55

Animation of Reverse Words in a String III Approach

Reverse Words in a String III Example

Input : "This is an example by LearnYard"
Output: "sihT si na elpmaxe yb draYnraeL"

Initial Setup

  • Input string s: "This is an example by LearnYard"
  • String length n: 33
  • Initial pointers: i = 0, j = 1

Iteration 1: Processing "This"

Step 1: Find word boundary

  • i = 0, j = 1
  • Inner while loop:
    • j = 1: s = 'h' ≠ ' ', so j++
    • j = 2: s = 'i' ≠ ' ', so j++
    • j = 3: s = 's' ≠ ' ', so j++
    • j = 4: s = ' ', loop breaks
  • Word found: "This" (indices 0 to 3)

Step 2: Reverse the word "This"

  • a = i = 0, b = j-1 = 3
  • Swap iterations:
    • a = 0, b = 3: swap s='T' with s='s' → "shiT"
    • a = 1, b = 2: swap s='h' with s='i' → "sihT"
    • a = 2, b = 1: condition a < b fails, exit loop
  • Result after reversing: "sihT is an example by LearnYard"

Step 3: Update pointers

  • i = j+1 = 5
  • j = i+1 = 6

Iteration 2: Processing "is"

Step 1: Find word boundary

  • i = 5, j = 6
  • Inner while loop:
    • j = 6: s = 's' ≠ ' ', so j++
    • j = 7: s = ' ', loop breaks
  • Word found: "is" (indices 5 to 6)

Step 2: Reverse the word "is"

  • a = 5, b = 6
  • Swap iterations:
    • a = 5, b = 6: swap s='i' with s='s' → "sihT si an example by LearnYard"
    • a = 6, b = 5: condition a < b fails, exit loop

Step 3: Update pointers

  • i = j+1 = 8
  • j = i+1 = 9

Iteration 3: Processing "an"

Step 1: Find word boundary

  • i = 8, j = 9
  • Inner while loop:
    • j = 9: s = 'n' ≠ ' ', so j++
    • j = 10: s = ' ', loop breaks
  • Word found: "an" (indices 8 to 9)

Step 2: Reverse the word "an"

  • a = 8, b = 9
  • Swap iterations:
    • a = 8, b = 9: swap s='a' with s='n' → "sihT si na example by LearnYard"
    • a = 9, b = 8: condition a < b fails, exit loop

Step 3: Update pointers

  • i = j+1 = 11
  • j = i+1 = 12

Iteration 4: Processing "example"

Step 1: Find word boundary

  • i = 11, j = 12
  • Inner while loop:
    • j = 12 to 17: all characters ≠ ' ', so j increments
    • j = 18: s = ' ', loop breaks
  • Word found: "example" (indices 11 to 17)

Step 2: Reverse the word "example"

  • a = 11, b = 17
  • Swap iterations:
    • a = 11, b = 17: swap 'e' with 'e' → no change
    • a = 12, b = 16: swap 'x' with 'l' → "sihT si na elxampe by LearnYard"
    • a = 13, b = 15: swap 'a' with 'p' → "sihT si na elpxmae by LearnYard"
    • a = 14, b = 14: condition a < b fails, exit loop

Step 3: Update pointers

  • i = j+1 = 19
  • j = i+1 = 20

Iteration 5: Processing "by"

Step 1: Find word boundary

  • i = 19, j = 20
  • Inner while loop:
    • j = 20: s = 'y' ≠ ' ', so j++
    • j = 21: s = ' ', loop breaks
  • Word found: "by" (indices 19 to 20)

Step 2: Reverse the word "by"

  • a = 19, b = 20
  • Swap iterations:
    • a = 19, b = 20: swap 'b' with 'y' → "sihT si na elpxmae yb LearnYard"
    • a = 20, b = 19: condition a < b fails, exit loop

Step 3: Update pointers

  • i = j+1 = 22
  • j = i+1 = 23

Iteration 6: Processing "LearnYard"

Step 1: Find word boundary

  • i = 22, j = 23
  • Inner while loop:
    • j = 23 to 32: all characters ≠ ' ', so j increments
    • j = 33: j >= n, loop breaks
  • Word found: "LearnYard" (indices 22 to 32)

Step 2: Reverse the word "LearnYard"

  • a = 22, b = 32
  • Swap iterations:
    • a = 22, b = 32: swap 'L' with 'd' → "sihT si na elpxmae yb dearnyarL"
    • a = 23, b = 31: swap 'e' with 'r' → "sihT si na elpxmae yb drarnearL"
    • a = 24, b = 30: swap 'a' with 'a' → no change
    • a = 25, b = 29: swap 'r' with 'Y' → "sihT si na elpxmae yb draYnearL"
    • a = 26, b = 28: swap 'n' with 'r' → "sihT si na elpxmae yb draYreanL"
    • a = 27, b = 27: condition a < b fails, exit loop

Step 3: Update pointers

  • i = j+1 = 34
  • j = i+1 = 35

Loop Termination

  • i = 34, n = 33
  • Condition i < n is false, main while loop exits

Reverse Words in a String III Algorithm

Step 1: Initialize Variables

Set up the necessary variables to track your position in the string and control your loops:

  • Store the string length for boundary checking
  • Create a pointer to mark the start of each word
  • Create another pointer to find the end of each word

Step 2: Set Up Main Loop Structure

Create a loop that will process each word in the string one by one:

  • Continue until you've processed all characters in the string
  • Use your starting pointer to check if you've reached the string end
  • Ensure the loop condition prevents out-of-bounds access

Step 3: Find Word Boundaries

Inside your main loop, locate where the current word ends:

  • Start from your second pointer position
  • Move forward until you hit a space character
  • Continue until you reach the end of the string
  • After this process, you'll know exactly where the current word begins and ends

Step 4: Set Up Reversal Pointers

Create two new pointers specifically for reversing the identified word:

  • One pointer starts at the beginning of the current word
  • Another pointer starts at the end of the current word
  • These will be used for the two-pointer swapping technique

Step 5: Reverse the Current Word

Use the classic two-pointer swapping technique:

  • Swap characters from both ends of the word
  • Move toward the center with each iteration
  • Continue until the pointers meet or cross each other
  • Each iteration should:
  • Swap one pair of characters
  • Move left pointer one step right
  • Move right pointer one step left

Step 6: Update Pointers for Next Word

After successfully reversing the current word:

  • Move past the space character to reach the next word
  • Set your starting pointer to the beginning of the next word
  • Position your second pointer one step ahead
  • Prepare for the next iteration of word boundary detection

Step 7: Handle the Last Word Edge Case

After your main loop completes:

  • Check if there's a final word that wasn't processed
  • This happens when the string doesn't end with a space character
  • Manually set up the boundaries for this last word
  • Apply the same reversal technique used for other words

Step 8: Return the Result

Complete the function:

  • Return the original string variable
  • All words should now be reversed in their original positions
  • The sentence structure remains intact
Reverse Words in a String III leetcode Solution
Reverse Words in a String III solution in C++ 
class Solution {
public:
    string reverseWords(string s) {
        // Get the total length of the input string
        int n = s.size();

        // Initialize pointers for word processing
        // i points to the start of current word
        // j is used to find the end of current word
        int i = 0;
        int j = 1;
        
        // Main loop to process each word in the string
        while(i < n) {
            // Find the end of current word by looking for space or end of string
            while(j < n && s[j] != ' ') j++;
            
            // Set up pointers for reversing the current word
            // a starts at beginning of word, b starts at end of word
            int a = i, b = j-1;
            
            // Reverse the current word using two-pointer technique
            while(a < b) {
                // Swap characters from both ends moving toward center
                swap(s[a], s[b]);
                // Move left pointer right and right pointer left
                a++;
                b--;
            }

            // Move to the next word
            // Skip the space character and position at start of next word
            i = j+1;
            // Set j one position ahead of i for next boundary search
            j = i+1;
        }
        
        // Handle the last word if string doesn't end with space
        // Set j to string length to mark end boundary
        j = n;
        // Set up pointers for the last word
        int a = i, b = j-1;
        
        // Reverse the last word using same technique
        while(a < b) {
            // Swap characters from both ends
            swap(s[a], s[b]);
            // Move pointers toward center
            a++;
            b--;
        }
        
        // Return the modified string with all words reversed
        return s;
    }
};

Reverse Words in a String III solution in Java 
class Solution {
    public String reverseWords(String s) {
        // Convert string to character array for in-place modification
        char[] chars = s.toCharArray();
        // Get the total length of the input string
        int n = chars.length;

        // Initialize pointers for word processing
        // i points to the start of current word
        // j is used to find the end of current word
        int i = 0;
        int j = 1;
        
        // Main loop to process each word in the string
        while(i < n) {
            // Find the end of current word by looking for space or end of string
            while(j < n && chars[j] != ' ') j++;
            
            // Set up pointers for reversing the current word
            // a starts at beginning of word, b starts at end of word
            int a = i, b = j-1;
            
            // Reverse the current word using two-pointer technique
            while(a < b) {
                // Swap characters from both ends moving toward center
                char temp = chars[a];
                chars[a] = chars[b];
                chars[b] = temp;
                // Move left pointer right and right pointer left
                a++;
                b--;
            }

            // Move to the next word
            // Skip the space character and position at start of next word
            i = j+1;
            // Set j one position ahead of i for next boundary search
            j = i+1;
        }
        
        // Handle the last word if string doesn't end with space
        // Set j to string length to mark end boundary
        j = n;
        // Set up pointers for the last word
        int a = i, b = j-1;
        
        // Reverse the last word using same technique
        while(a < b) {
            // Swap characters from both ends
            char temp = chars[a];
            chars[a] = chars[b];
            chars[b] = temp;
            // Move pointers toward center
            a++;
            b--;
        }
        
        // Convert character array back to string and return
        return new String(chars);
    }
}

Reverse Words in a String III solution in Python 
class Solution:
    def reverseWords(self, s: str) -> str:
        # Convert string to list for in-place modification
        chars = list(s)
        # Get the total length of the input string
        n = len(chars)

        # Initialize pointers for word processing
        # i points to the start of current word
        # j is used to find the end of current word
        i = 0
        j = 1
        
        # Main loop to process each word in the string
        while i < n:
            # Find the end of current word by looking for space or end of string
            while j < n and chars[j] != ' ':
                j += 1
            
            # Set up pointers for reversing the current word
            # a starts at beginning of word, b starts at end of word
            a, b = i, j-1
            
            # Reverse the current word using two-pointer technique
            while a < b:
                # Swap characters from both ends moving toward center
                chars[a], chars[b] = chars[b], chars[a]
                # Move left pointer right and right pointer left
                a += 1
                b -= 1

            # Move to the next word
            # Skip the space character and position at start of next word
            i = j + 1
            # Set j one position ahead of i for next boundary search
            j = i + 1
        
        # Handle the last word if string doesn't end with space
        # Set j to string length to mark end boundary
        j = n
        # Set up pointers for the last word
        a, b = i, j-1
        
        # Reverse the last word using same technique
        while a < b:
            # Swap characters from both ends
            chars[a], chars[b] = chars[b], chars[a]
            # Move pointers toward center
            a += 1
            b -= 1
        
        # Convert list back to string and return
        return ''.join(chars)

Reverse Words in a String III solution in Javascript 
/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    // Convert string to array for in-place modification
    let chars = s.split('');
    // Get the total length of the input string
    let n = chars.length;

    // Initialize pointers for word processing
    // i points to the start of current word
    // j is used to find the end of current word
    let i = 0;
    let j = 1;
    
    // Main loop to process each word in the string
    while(i < n) {
        // Find the end of current word by looking for space or end of string
        while(j < n && chars[j] !== ' ') j++;
        
        // Set up pointers for reversing the current word
        // a starts at beginning of word, b starts at end of word
        let a = i, b = j-1;
        
        // Reverse the current word using two-pointer technique
        while(a < b) {
            // Swap characters from both ends moving toward center
            let temp = chars[a];
            chars[a] = chars[b];
            chars[b] = temp;
            // Move left pointer right and right pointer left
            a++;
            b--;
        }

        // Move to the next word
        // Skip the space character and position at start of next word
        i = j+1;
        // Set j one position ahead of i for next boundary search
        j = i+1;
    }
    
    // Handle the last word if string doesn't end with space
    // Set j to string length to mark end boundary
    j = n;
    // Set up pointers for the last word
    let a = i, b = j-1;
    
    // Reverse the last word using same technique
    while(a < b) {
        // Swap characters from both ends
        let temp = chars[a];
        chars[a] = chars[b];
        chars[b] = temp;
        // Move pointers toward center
        a++;
        b--;
    }
    
    // Convert array back to string and return
    return chars.join('');
};

Reverse Words in a String III: Complexity Analysis

Time Complexity: O(n)

The time complexity of our approach is linear, where n is the length of the input string. Let's break down why this is the case by analyzing each component of our algorithm.

Main Loop Execution:

  • The outer while loop runs exactly once for each word in the string
  • If there are w words in the string, the loop executes w times
  • However, the total work done across all iterations is what matters for complexity analysis

Word Boundary Detection:

  • The inner while loop that finds word boundaries traverses each character exactly once
  • Each character in the string is visited exactly once during the boundary detection phase
  • This contributes O(n) to our total complexity

Word Reversal Process:

  • For each word, we perform character swaps using the two-pointer technique
  • If a word has length L, we perform L/2 swaps
  • The total number of swaps across all words equals the total number of characters divided by 2
  • This gives us O(n/2) which simplifies to O(n)

Pointer Updates:

  • Moving pointers between words takes constant time O(1) per word
  • With w words, this contributes O(w) to the total complexity
  • Since w ≤ n (number of words cannot exceed string length), this doesn't affect our overall complexity

Mathematical Breakdown

Let's consider a string with words of lengths L₁, L₂, L₃, ..., Lw:

Total character processing:

  • Boundary detection: L₁ + L₂ + L₃ + ... + Lw = n
  • Character swaps: (L₁/2) + (L₂/2) + (L₃/2) + ... + (Lw/2) = n/2
  • Total operations: n + n/2 = 1.5n

Simplified complexity: O(1.5n) = O(n)

Space Complexity: O(1) /output

To understand the space complexity. It is crucial to understand the distinction between auxiliary space and total space complexity:

  • Auxiliary Space: The extra space or temporary space used by an algorithm, excluding the input and output space.
  • Total Space Complexity: The total space taken by the algorithm with respect to input size, including both auxiliary space and space used by the input and output

Auxiliary Space Complexity: O(1)

Our algorithm uses constant auxiliary space because it only requires a fixed number of additional variables regardless of input size:

Variables Used:

  • n - stores the string length (4 bytes)
  • i - pointer for word start position (4 bytes)
  • j - pointer for word boundary detection (4 bytes)
  • a - left pointer for word reversal (4 bytes)
  • b - right pointer for word reversal (4 bytes)

Total auxiliary space: 20 bytes (constant)

Why It's O(1):

  • No additional data structures are created
  • No recursive calls that consume stack space
  • No dynamic memory allocation occurs
  • The number of variables remains fixed regardless of string length
  • All operations are performed in-place on the input string

Total Space Complexity: O(n)

The total space complexity includes auxiliary space as well as input and output space:

Input Space: O(n) - where n is the length of the input string

Output Space O(n) - Where n is the length of the output string which is modified input string where each word is reversed.

Auxiliary Space: O(1) - constant extra variables


The Total Overall Space Complexity: O(n) + O(n) + O(1) = O(n)

Similar Problems

Now we have successfully tackled this problem, let's try these similar problems:-

1. Reverse Words in a String

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.