What is the time complexity of Reverse Words in a String?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Reverse Words in a String?

This problem uses Two Pointers, String. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Reverse Words in a String?

Insight 1: Splitting the string into words is a crucial first step. Using the built-in `split()` method handles multiple spaces correctly. Insight 2: Reversing the order of the words, which can be done using built-in functions or custom loops.

Which companies ask LeetCode 151. Reverse Words in a String in interviews?

This problem is frequently asked at Accenture, Capgemini, Cisco, Deloitte, HPE and 13 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Reverse Words in a String - LeetCode 151 Solution

Reverse Words in a String - Complete Solution Guide

Reverse Words in a String is LeetCode problem 151, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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. Example 1: Input: s = "the sky is blue" Output: "blue

Detailed Explanation

The problem requires you to reverse the order of words in a given string. The input string may contain leading or trailing spaces, or multiple spaces between words. The output string must contain the words in reversed order, separated by a single space, and must not have any leading or trailing spaces.

Solution Approach

The provided solutions follow a common three-step approach: splitting the input string into individual words, reversing the order of these words, and then joining them back into a single string with a single space as a separator. The `split()` method automatically handles leading, trailing and multiple spaces between words.

Step-by-Step Algorithm

Step 1: Split the input string into a list (or array) of words using spaces as delimiters. The `split()` method is used for this purpose in Python, Java, and C++. In C, manual parsing is implemented to extract words.
Step 2: Reverse the order of the elements in the list (or array). Python uses slicing `[::-1]`, Java uses `Collections.reverse()`, and C++ uses `std::reverse()`.
Step 3: Join the reversed list of words back into a single string, using a single space as a separator between words. Python uses `' '.join()`, Java uses `String.join()`, C++ manually builds the string with spaces. The C solution also manually builds the string.
Step 4: (C only) Handle memory allocation and deallocation carefully to prevent memory leaks. The C solution requires explicit memory management for the array of words and the resulting string, including error handling for allocation failures.

Key Insights

Insight 1: Splitting the string into words is a crucial first step. Using the built-in `split()` method handles multiple spaces correctly.
Insight 2: Reversing the order of the words, which can be done using built-in functions or custom loops.
Insight 3: Joining the reversed words back into a single string with a single space between each word.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Two Pointers, String.

Companies

Asked at: Accenture, Capgemini, Cisco, Deloitte, HPE, Infosys, Intel, Morgan Stanley, Paytm, Snap, TikTok, Visa, Walmart Labs, Wayfair, Yelp, Zoho, Zopsmart, tcs.

Reverse Words in a String | LeetCode 151

Medium

Two Pointers String

Time: O(n)Space: O(n)

Solution Code

Available in:

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class Solution {
    public String reverseWords(String s) {
        // Split the string into a list of words.
        // s.split() handles multiple spaces and leading/trailing spaces correctly.
        List<String> words = Arrays.asList(s.split(" "));
        
        // Reverse the list of words.
        Collections.reverse(words);
        
        // Join the words back into a string with a single space separator.
        return String.join(" ", words);
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 151: Reverse Words in a String - Detailed explanation and solution approaches.

Topics

Two Pointers String

Companies

AccentureCapgeminiCiscoDeloitteHPEInfosysIntelMorgan Stanley

Stats

Difficulty:Medium

Languages:4

Companies:18

Problem #:151

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

4 steps

1
Step 1: Split the input string into a list (or array) of words using spaces as delimiters. The `split()` method is used for this purpose in Python, Java, and C++. In C, manual parsing is implemented to extract words.
2
Step 2: Reverse the order of the elements in the list (or array). Python uses slicing `[::-1]`, Java uses `Collections.reverse()`, and C++ uses `std::reverse()`.
3
Step 3: Join the reversed list of words back into a single string, using a single space as a separator between words. Python uses `' '.join()`, Java uses `String.join()`, C++ manually builds the string with spaces. The C solution also manually builds the string.
4
Step 4: (C only) Handle memory allocation and deallocation carefully to prevent memory leaks. The C solution requires explicit memory management for the array of words and the resulting string, including error handling for allocation failures.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is O(n) because we iterate through the string at most a constant number of times. Splitting, reversing, and joining all depend linearly on the number of characters/words in the string. The space complexity is O(n) because we create a list/array to store the words.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

In-place reversal (if string is mutable)

If the string is mutable, it's possible to reverse the entire string and then reverse each word individually. This avoids extra space for storing the words.

Time: O(n)Space: O(1)

Trade-offs: This approach is more complex to implement and only applicable if the string is mutable. It also might not be available in all languages. The problem description suggests this in the follow-up.

Using a Stack

Split the string into words and push each word onto a stack. Then, pop the words from the stack and join them with a single space. This achieves the reversal.

Time: O(n)Space: O(n)

Trade-offs: Using a stack is conceptually clear but generally doesn't offer any performance advantages over using `split()` and `reverse()`. It also takes up O(n) space to store the words in the stack.

✨

Key Insights

1Insight 1: Splitting the string into words is a crucial first step. Using the built-in `split()` method handles multiple spaces correctly.
2Insight 2: Reversing the order of the words, which can be done using built-in functions or custom loops.
3Insight 3: Joining the reversed words back into a single string with a single space between each word.

📚

Key Terms Explained

For Students

Two Pointers

Using two indices to traverse data from different positions simultaneously.

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Leading and trailing spaces. The `split()` method handles these correctly by removing them.
Edge case 2: Multiple spaces between words. The `split()` method treats multiple spaces as a single delimiter, resulting in a single space between words in the reversed string.
Edge case 3: Empty input string (or a string containing only spaces). The `split()` method returns an empty list, which results in an empty string after joining in most languages. The C version will handle empty input without crashing as well.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to handle leading/trailing spaces. The `split()` method addresses this, but manual parsing requires careful handling.

✗Common mistake 2: Failing to reduce multiple spaces between words to a single space. Again, `split()` handles this automatically.

✗Common mistake 3: In languages like C, forgetting to free the dynamically allocated memory, leading to memory leaks. The C solution shows the correct allocation and freeing.

✗Common mistake 4: Assuming the string is mutable when it is not (e.g., in Java, strings are immutable), and attempting in-place modifications without creating a new string.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Text processing and manipulation, such as reversing the order of sentences or phrases.

🏦Real-world scenario 2: Parsing user input and rearranging elements, like in a command-line interpreter where commands might need to be processed in reverse order.

🎮Real-world scenario 3: In search engines or databases, reversing strings can be useful for indexing or searching for patterns within text data.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

The two-pointer technique is powerful for sorted arrays. The key insight is recognizing when elements can be processed from both ends simultaneously.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

The most common mistake is not handling the case when pointers meet. Always consider the termination condition.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 30, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 14

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 7

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJun 30

❓

Frequently Asked Questions

How do I avoid infinite loops with two pointers?

Always ensure your loop condition guarantees termination (typically left < right or slow != fast). Move at least one pointer in each iteration, and handle edge cases where pointers might not move (like skipping duplicates). Draw out pointer movement on paper first.

What is the sliding window technique for string problems?

Sliding window maintains a "window" of characters with two pointers. Expand the right pointer to include characters, shrink from left when window violates constraints. Useful for substring problems, anagrams, and longest/shortest substring with properties.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Reverse Words in a String"?

For this medium-level Two Pointers problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether string techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?