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