LeetCode Challenge: 151. Reverse Words in a String - JavaScript Solution 🚀

#javascript #programming #leetcode #interview

Top Interview 150

Reversing the words in a string while handling multiple spaces efficiently is a common problem in string manipulation. Let's tackle LeetCode 151: Reverse Words in a String with an optimized solution and without using predefined methods like split or trim.

🚀 Problem Description

Given a string s, reverse the order of the words in the string:

A word is defined as a sequence of non-space characters.
Return the reversed string with a single space between the words.
Extra spaces before, after, or between words should be removed.

💡 Examples

Example 1

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

Example 2

Input: s = "  hello world  "  
Output: "world hello"  
Explanation: Leading and trailing spaces are removed.

Example 3

Input: s = "a good   example"  
Output: "example good a"  
Explanation: Multiple spaces are reduced to a single space.

🏆 Optimized JavaScript Solution

We will create a solution without relying on split or trim, aiming for O(n) time complexity and O(1) extra space.

Implementation

var reverseWords = function(s) {
    let n = s.length;
    let trimmed = "";
    let i = 0;

    while (i < n) {
        while (i < n && s[i] === ' ') i++;
        if (i >= n) break;

        let start = i;
        while (i < n && s[i] !== ' ') i++;
        if (trimmed.length > 0) trimmed = " " + trimmed;
        trimmed = s.slice(start, i) + trimmed;
    }

    return trimmed;
};

🔍 How It Works

Remove Spaces and Extract Words:
- Traverse the string while skipping spaces.
- Identify words by their start and end indices.
- Prepend each word to the result string.
Handle Single Spaces Between Words:
- Add a space before appending a word only if the result string is not empty.
Return the Result:
- By appending words in reverse order, we ensure that the words appear in reversed sequence.

🔑 Complexity Analysis

> Time Complexity: O(n), where n is the length of the string.
- We traverse the string once while extracting words.
> Space Complexity: O(n), for the result string.

📋 Dry Run

Input: " hello world "

Output: "world hello"

✨ Pro Tips for Optimization

In-place Solution (Follow-Up):
- Reverse the entire string.
- Reverse each word in the reversed string.
- Remove extra spaces.

Here’s the in-place implementation:

var reverseWords = function(s) {
    const reverse = (arr, start, end) => {
        while (start < end) {
            [arr[start], arr[end]] = [arr[end], arr[start]];
            start++;
            end--;
        }
    };

    let arr = Array.from(s);
    let n = arr.length;

    reverse(arr, 0, n - 1);

    let start = 0;
    for (let i = 0; i <= n; i++) {
        if (i === n || arr[i] === ' ') {
            reverse(arr, start, i - 1);
            start = i + 1;
        }
    }

    let result = [];
    for (let i = 0; i < n; i++) {
        if (arr[i] !== ' ' || (result.length > 0 && result[result.length - 1] !== ' ')) {
            result.push(arr[i]);
        }
    }

    if (result[result.length - 1] === ' ') result.pop();

    return result.join('');
};