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

1. 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.

2. Handle Single Spaces Between Words:

   • Add a space before appending a word only if the result string is not empty.

3. 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

1. 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('');
};

🔑 Complexity Analysis (In-Place Solution)

• Time Complexity: O(n), due to three passes over the string.
• Space Complexity: O(1), as no additional arrays or data structures are used.

📚 Learn More

Check out the full explanation and code walkthrough on my Dev.to post:
👉 Reverse Words in a String - JavaScript Solution

What’s your approach to solving this problem? Let’s discuss below! 🚀

JavaScript #LeetCode #CodingInterview #ProblemSolving