Reverse Words In String Solution for Wipro

Company: Wipro · Difficulty: Easy · Topics: String, Two Pointers

Problem Statement

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.

Examples

Example 1:

Input: s = "the sky is blue"

Output: "blue is sky the"

Explanation: The words are reversed while maintaining single space separation.

Example 2:

Input: s = " hello world "

Output: "world hello"

Explanation: Leading and trailing spaces are removed, and multiple spaces between words are reduced to single spaces.

Intuition

We need to split the string into words, reverse their order, and join them back with single spaces. We also need to handle leading/trailing spaces and multiple spaces between words.

Approach

Approach 1: Split and Reverse (Optimal)

1. Split the string by whitespace to get words

2. Filter out empty strings (from multiple spaces)

3. Reverse the array of words

4. Join with single space

Approach 2: Two Pointers

1. Trim leading and trailing spaces

2. Use two pointers to find word boundaries

3. Extract words and store in array

4. Reverse and join

Approach 3: Stack

1. Split string into words

2. Push words onto stack

3. Pop words to get reverse order

4. Join with spaces

Dry Run

Let's trace through Example 1: s = "the sky is blue"

Split and Reverse Approach:

Split: ["the", "sky", "is", "blue"]
Filter: ["the", "sky", "is", "blue"] (no empty strings)
Reverse: ["blue", "is", "sky", "the"]
Join: "blue is sky the"

Example 2: s = " hello world "

Split: ["", "", "hello", "world", "", ""]
Filter: ["hello", "world"]
Reverse: ["world", "hello"]
Join: "world hello"

Key Insights

1. String Splitting: Use split() to separate words

2. Space Handling: Filter out empty strings from multiple spaces

3. Array Reversal: Simple array reversal gives word reversal

4. String Joining: Join with single space for clean output

Edge Cases

1. Leading spaces: " hello world" → "world hello"

2. Trailing spaces: "hello world " → "world hello"

3. Multiple spaces: "hello world" → "world hello"

4. Single word: "hello" → "hello"

5. Empty string: "" → ""

Time and Space Complexity

Time Complexity: O(n) - Single pass through string
Space Complexity: O(n) - Space for storing words