Skip to main content

Two Pointer

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

Problem Description:

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.
Problem Description: Reverse Words in a String

Examples:

Input: s = "the sky is blue"
Output: "blue is sky the"

Input: s = " hello world "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Input: s = "a good example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Constraints:

  • 1 <= s.length <= 104
  • s contains English letters (upper-case and lower-case), digits, and spaces ' '.
  • There is at least one word in s.

Approach

Intuition:

If we understand the problem carefully, we can see that we have three things to deal with:

  • The leading spaces (unwanted spaces before the first word),
  • The spaces separating two words, and
  • The trailing spaces (extra spaces after the last word).

The goal is to reverse the words in a string. That means the last word should appear first, the second-last word should appear second, and so on. Additionally:

  • Words must be separated by a single space,
  • There should be no leading or trailing spaces in the final result.

Imagine the input string as a messy or cluttered sentence where meaningful words are buried between irregular spaces. Despite this, each word is a continuous block of characters without spaces inside.

This gives us a clear strategy: find and extract each word, then collect them in reverse order.

To put everything together we will:

  1. Find each word while skipping unnecessary spaces.
  2. Extract the word and store it in a list or array which can hold string.
  3. After collecting all words, reverse the vector.
  4. Finally, join the words using single spaces to build the final clean result.
💡
While we can refrain from using any list or array of string and could directly append each word we find to a temporary result string as we discover them.

We haven't used this approach in our solution for an important performance reason. When you repeatedly append strings to an existing string, each append operation might require creating a new string and copying all the previous content, which can be quite expensive computationally.

In the worst case, this repeated string concatenation can push our algorithm's time complexity up to O(n²), where n is the length of the input string. By first collecting all words in a list or array and then processing them, we maintain a more efficient O(n) time complexity, ensuring our solution performs well even with larger inputs.

How to find each word in the input string?

To answer this, we can make use of an observation which is, each word is a continuous block of characters (anything except spaces).

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.

Once we identify a word using our two pointers, we extract the word and store it in a data structure that can hold multiple words in order. In most programming languages, this would be an array or list of strings.

After we've collected all the words, we can build our final sentence by going through our list in reverse order, taking the last word first, then the second-to-last word, and so on.

Example:

Let's say our input is: "the sky is blue"

Step 1: Our word-finding process identifies: "the", "sky", "is", "blue"
Step 2: We store these in our list: ["the", "sky", "is", "blue"]
Step 3: We process the list in reverse order: "blue", "is", "sky", "the"
Step 4: We join them with single spaces: "blue is sky the"

This gives us our final answer with proper formatting and no extra spaces.

Why This Approach Works Well?

This method is effective because it separates the concerns. We handle word extraction separately from word reversal and formatting. This makes the solution easier to understand and implement correctly.

The two pointer technique ensures we process each character in the string efficiently, and storing words in a list allows us to easily reverse their order when building the final result.

0:00
/1:25

Approach Animation: Reverse Words in a String

Reverse Words in a String Example

Input: s = " good things take time "
Output: "time take things good"

s = " good things take time "

Initial state:

  • n = 24
  • words = []
  • ans = ""
  • i = 0

Main while loop iterations:

  1. Skip leading spaces:
    i = 0 → 1 (s[1] = 'g')
  2. Find word "good"
    j = 2 → 5 (s[5] = ' ')
    word = s.substr(1, 4) = "good"
    words = ["good"]
    i = j + 1 = 6
  3. Find word "things"
    j = 7 → 12 (s[12] = ' ')
    word = s.substr(6, 6) = "things"
    words = ["good", "things"]
    i = j+1 = 13
  4. Find word "take"
    j = 14 → 17
    word = s.substr(13, 4) = "take"
    words = ["good", "things", "take"]
    i = j+1 = 18
  5. Find word "time"
    j = 19 → 22
    word = s.substr(18, 4) = "time"
    words = ["good", "things", "take", "time"]
    i = j+1 = 23
  6. Skip trailing spaces:
    i = 23 → 24 → loop ends

Reverse and build ans from words:

  • i = 3 → 0
  1. i = 3, words[3] = "time" → ans = "time"
  2. i = 2, words[2] = "take" → ans = "time take"
  3. i = 1, words[1] = "things" → ans = "time take things"
  4. i = 0, words[0] = "good" → ans = "time take things good"

Final output: "time take things good"

Reverse Words in a String Algorithm

Step 1: Initialize Variables

  • Get the length of the input string s
  • Declare a vector<string> to store words
  • Declare a result string ans
  • Initialize pointer i = 0

Step 2: Loop Through the String to Extract Words

  • Use a while(i < n) loop
  • Skip leading/multiple spaces.
  • Set j = i + 1
  • Move j to the end of the current word
  • Extract the word using s.substr(i, j - i)
  • If the word is not empty, push it to the words vector
  • Move i = j + 1 to process the next word


Step 3: Reverse the Words and Build Result

  • Loop from the end of the words vector to the start
  • For each word, append it to ans character by character
  • After each word (except the last), add a space

Step 4: Return the Result

Reverse Words in a String leetcode Solutions
Reverse Words in a String solution in C++ 
class Solution {
public:
    string reverseWords(string s) {
        // Get the length of the input string
        int n = s.size();

        // Vector to store extracted words from the string
        vector<string> words;

        // Final answer string to store the reversed sentence
        string ans = "";

        // Initialize index pointer i to start scanning the string
        int i = 0;

        // Loop until we reach the end of the string
        while (i < n) {
            // Skip all leading spaces until a non-space character is found
            while (i < n && s[i] == ' ') {
                i++;
            }

            // Set another pointer j starting from next character after i
            int j = i + 1;

            // Move j forward until a space or end of string is reached
            while (j < n && s[j] != ' ') {
                j++;
            }

            // Extract the substring representing a word from index i to j-1
            string word = s.substr(i, j - i);

            // If the extracted word is not empty, add it to the words vector
            if (!word.empty()) {
                words.push_back(word);
            }

            // Move i beyond the end of the current word to continue scanning
            i = j + 1;
        }

        // Build the final reversed string by traversing the words vector backwards
        for (int idx = (int)words.size() - 1; idx >= 0; --idx) {
            // Append each character of the current word to the answer string
            for (auto &c : words[idx]) {
                ans.push_back(c);
            }
            // Append a space after each word except the last one
            if (idx != 0) {
                ans.push_back(' ');
            }
        }

        // Return the final reversed sentence with cleaned spacing
        return ans;
    }
};

Reverse Words in a String solution in java 
class Solution {
    public String reverseWords(String s) {
        // Length of the input string
        int n = s.length();

        // List to store extracted words
        ArrayList<String> words = new ArrayList<>();

        // Index pointer to scan the string
        int i = 0;

        // Loop until the end of the string
        while (i < n) {
            // Skip leading spaces
            while (i < n && s.charAt(i) == ' ') {
                i++;
            }

            // Start of the word
            int j = i + 1;

            // Move j until space or end of string
            while (j < n && s.charAt(j) != ' ') {
                j++;
            }

            // Extract the word from s.substring(i, j)
            if (i < n) {
                String word = s.substring(i, j);

                // If word is not empty, add to list
                if (!word.isEmpty()) {
                    words.add(word);
                }
            }

            // Move i past the current word
            i = j + 1;
        }

        // Build reversed string by concatenating words in reverse order separated by space
        StringBuilder ans = new StringBuilder();

        for (int k = words.size() - 1; k >= 0; k--) {
            ans.append(words.get(k));

            if (k != 0) {
                ans.append(" ");
            }
        }

        // Return the final reversed words string
        return ans.toString();
    }
};

Reverse Words in a String solution in Python 
class Solution:
    def reverseWords(self, s: str) -> str:
        # Length of the input string
        n = len(s)
        
        # List to store extracted words
        words = []
        
        # Index pointer to scan the string
        i = 0
        
        # Loop until the end of the string
        while i < n:
            # Skip leading spaces
            while i < n and s[i] == ' ':
                i += 1
            
            # Start of the word
            j = i + 1
            
            # Move j until space or end of string
            while j < n and s[j] != ' ':
                j += 1
            
            # Extract the word from s[i:j]
            word = s[i:j]
            
            # If word is not empty, add to list
            if word:
                words.append(word)
            
            # Move i past the current word
            i = j + 1
        
        # Build reversed string by joining words in reverse order with a single space
        ans = ' '.join(words[::-1])
        
        return ans

Reverse Words in a String solution in Javascript 
/**
 * Function to reverse words in a string
 * @param {string} s - Input string with possible extra spaces
 * @return {string} - String with words reversed, single spaces between words, no leading/trailing spaces
 */
var reverseWords = function(s) {
    // Length of the input string
    const n = s.length;

    // Array to hold extracted words
    const words = [];

    // Pointer to traverse the string
    let i = 0;

    // Loop through the string to extract all words
    while (i < n) {
        // Skip any leading spaces before a word
        while (i < n && s[i] === ' ') {
            i++;
        }

        // Pointer to find the end of the current word
        let j = i + 1;

        // Move j until a space or end of string is found
        while (j < n && s[j] !== ' ') {
            j++;
        }

        // Extract the word and add to words array if not empty
        if (i < n) {
            const word = s.substring(i, j);
            if (word.length > 0) {
                words.push(word);
            }
        }

        // Move i to the character after the current word
        i = j + 1;
    }

    // Build the result string by concatenating words in reverse order
    let ans = '';
    for (let k = words.length - 1; k >= 0; k--) {
        ans += words[k];
        if (k !== 0) {
            ans += ' ';
        }
    }

    // Return the final reversed string
    return ans;
};

Reverse Words in a String Complexity Analysis

Time Complexity: O(n)

Let's analyze the time complexity of this approach step by step:

Let:

  • n be the length of the input string s
  • k be the number of words in the string
  • L be the total number of non-space characters in s (i.e., the sum of the lengths of all words)

Phase 1: Extract Words

  • Scans the entire string once using two pointers (i and j), skipping spaces and extracting words.
  • Each character is visited at most twice (once by i, once by j), so this phase runs in O(n) time.

Phase 2: Build Final String

  • Iterates over the vector<string> of k words in reverse.
  • For each word, appends its characters to the result string.
  • Total characters appended equals L, and at most k−1 spaces are added between words.
  • This phase takes O(L + k) time.

Final Time Complexity

  • Overall time complexity is O(n + L + k)
  • Since L ≤ n and k ≤ n, the dominant term is O(n)

Final Time Complexity: O(n)

Space Complexity: O(n)

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

Let:

  • n = length of the input string s
  • L = total number of non-space characters
  • k = number of words in the string

Auxiliary Space Complexity
These are extra data structures created during execution:

  • vector<string> words:
    Stores each extracted word.
    • Space used: O(L) (total length of all words)
  • Temporary variables and substrings (e.g., word = s.substr(...)):
    • These are reused and don't grow beyond a single word's length at a time.
    • Space used: negligible, bounded by O(word length) → within O(L)

Total Auxiliary Space: O(L)

Since L ≤ n. So, O(n)

Total Space Complexity
Includes the auxiliary space as well as input and output space:

  • Input string s:
    • Not counted in auxiliary but part of total memory used → O(n)
  • Output string ans:
    Stores the final reversed sentence.
    • Space used: O(L + k)
      (includes all the non space characters, the k-1 spaces between words)
  • Auxiliary space (from above): O(L)

Since L + k ≤ n + n = 2n, overall:

Hence, overall space complexity is: O(n)

Similar Problems

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

1. Reverse Words in a String III

Given a string s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.