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