Jobs

Interviews

Discussions

Reverse Words in a String II

Medium

Asked by:

More companies

49 views

Topics:

ArraysStringsTwo Pointers

Given a character array 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 a single space.

Your solution must modify s in-place.

Example 1:

Input: s = ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
Output: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]

Example 2:

Input: s = ["a"]
Output: ["a"]

Constraints:

1 <= s.length <= 10⁵
s[i] is an English letter (upper or lower-case), digit, or space.
There is at least one word in s.
All the words in s are separated by a single space.
There are no leading or trailing spaces.

Try coding it in LeetCode

Reverse Words in a String II

Medium

Asked by:

49 views

Topics:

ArraysStringsTwo Pointers

Given a character array 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 a single space.

Your solution must modify s in-place.

Example 1:

Input: s = ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
Output: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]

Example 2:

Input: s = ["a"]
Output: ["a"]

Constraints:

1 <= s.length <= 10⁵
s[i] is an English letter (upper or lower-case), digit, or space.
There is at least one word in s.
All the words in s are separated by a single space.
There are no leading or trailing spaces.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Will the input string contain leading or trailing spaces, and should I trim them?
Can the input string contain multiple spaces between words, and how should I handle them?
Is the input guaranteed to contain at least one word, or could it be an empty string?
Should the reversal be done in-place, modifying the original character array directly?
Are there any special characters or non-alphanumeric characters that I should be aware of?

Brute Force Solution

Approach

The brute force method solves this by looking at every possible combination. Think of it like manually trying out different arrangements of the words in the string. We will reverse the entire string, then reverse each word individually.

Here's how the algorithm would work step-by-step:

First, take the entire string and reverse it completely. So the last letter becomes the first, and so on.
Next, go through the reversed string word by word.
For each word you find, reverse that word individually. This puts the letters of each word back in the correct order, but keeps the words themselves in the reversed order.

Code Implementation

def reverse_words(list_of_characters):
    def reverse_substring(list_of_characters, start, end):
        while start < end:
            list_of_characters[start], list_of_characters[end] = list_of_characters[end], list_of_characters[start]
            start += 1
            end -= 1

    # Reverse the entire string to put words in reverse order
    reverse_substring(list_of_characters, 0, len(list_of_characters) - 1)

    start_index = 0
    for index in range(len(list_of_characters) + 1):
        if index == len(list_of_characters) or list_of_characters[index] == ' ':
            # Reverse each word to get letters in correct order
            reverse_substring(list_of_characters, start_index, index - 1)

            start_index = index + 1

Big(O) Analysis

Time Complexity

O(n) – The algorithm first reverses the entire string of length n. This reversal takes O(n) time. Then, it iterates through the reversed string again, identifying each word and reversing it. Reversing each word also takes time proportional to the length of that word. Since all the word lengths added together equals the length of the string n, the total time spent reversing individual words is also O(n). Therefore, the overall time complexity is O(n) + O(n), which simplifies to O(n).

Space Complexity

O(1) – The algorithm reverses the entire string in-place, meaning it modifies the input directly. The individual word reversals are also performed in-place using a constant number of variables to track start and end positions within the string. Therefore, no auxiliary data structures that scale with the input size N (the length of the string) are used. The algorithm's space usage remains constant, independent of the input string's length.

Optimal Solution

Approach

The trick to reversing words in place is to first reverse the entire string. After that, reverse each word individually. This approach avoids needing extra memory to store the reversed string or individual words.

Here's how the algorithm would work step-by-step:

Reverse the entire string of characters. So, if the original string was 'the sky is blue', it becomes 'eulb si yks eht'.
Now, go through the reversed string and reverse each word separately. In our example, 'eulb' becomes 'blue', 'si' becomes 'is', 'yks' becomes 'sky', and 'eht' becomes 'the'.
The final result after reversing each word is 'blue is sky the', which is the desired output.

Code Implementation

def reverse_words(list_of_characters):
    def reverse_range(list_to_reverse, start_index, end_index):
        while start_index < end_index:
            list_to_reverse[start_index], list_to_reverse[end_index] = list_to_reverse[end_index], list_to_reverse[start_index]
            start_index += 1
            end_index -= 1

    # First, reverse the entire string.
    reverse_range(list_of_characters, 0, len(list_of_characters) - 1)

    start_of_word_index = 0
    for index in range(len(list_of_characters) + 1):
        # Identify word boundaries using spaces
        if index == len(list_of_characters) or list_of_characters[index] == ' ':
            # Reverse each word individually.
            reverse_range(list_of_characters, start_of_word_index, index - 1)

            # Move the start index to the next word.
            start_of_word_index = index + 1

Big(O) Analysis

Time Complexity

O(n) – The algorithm first reverses the entire string, which takes O(n) time where n is the length of the string. Then, it iterates through the reversed string to reverse each word. Reversing each word also takes O(n) time in total because, in the worst case, every single character must be individually accessed and flipped during these smaller reversals. Since we perform two O(n) operations sequentially, the overall time complexity is O(n) + O(n) which simplifies to O(n).

Space Complexity

O(1) – The algorithm operates in-place, meaning it modifies the original string directly. It primarily uses a constant number of variables for swapping characters during the reversal process and to keep track of word boundaries. Therefore, the auxiliary space required does not depend on the size of the input string N and remains constant.

Edge Cases

Case	How to Handle
Null or empty input string	Return immediately or throw an IllegalArgumentException as appropriate for the language.
String with only spaces	Treat multiple spaces as single spaces, resulting in an empty or single-space string after reversal.
String with leading/trailing spaces	Trim leading and trailing spaces before reversing the words to avoid extra spaces in the output.
Single word string	The reversed string will be the same as the original string, so return the original.
String with consecutive multiple spaces between words	Reduce multiple spaces to single spaces during processing.
Maximum length string (memory constraints)	Ensure the solution doesn't exceed memory limits and potentially consider in-place reversal if memory is a concern.
String containing non-ASCII characters	Ensure the string reversal algorithm handles Unicode characters correctly, using UTF-8 encoding or similar.
Integer overflow when calculating lengths or indices	Use appropriate data types (e.g., long) or validate input lengths to prevent integer overflow.

Null or empty input string

How to Handle:

Return immediately or throw an IllegalArgumentException as appropriate for the language.

String with only spaces

How to Handle:

Treat multiple spaces as single spaces, resulting in an empty or single-space string after reversal.

String with leading/trailing spaces

How to Handle:

Trim leading and trailing spaces before reversing the words to avoid extra spaces in the output.

Single word string

How to Handle:

The reversed string will be the same as the original string, so return the original.

String with consecutive multiple spaces between words

How to Handle:

Reduce multiple spaces to single spaces during processing.

Maximum length string (memory constraints)

How to Handle:

Ensure the solution doesn't exceed memory limits and potentially consider in-place reversal if memory is a concern.

String containing non-ASCII characters

How to Handle:

Ensure the string reversal algorithm handles Unicode characters correctly, using UTF-8 encoding or similar.

Integer overflow when calculating lengths or indices

How to Handle:

Use appropriate data types (e.g., long) or validate input lengths to prevent integer overflow.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Will the input string contain leading or trailing spaces, and should I trim them?
Can the input string contain multiple spaces between words, and how should I handle them?
Is the input guaranteed to contain at least one word, or could it be an empty string?
Should the reversal be done in-place, modifying the original character array directly?
Are there any special characters or non-alphanumeric characters that I should be aware of?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, take the entire string and reverse it completely. So the last letter becomes the first, and so on.
Next, go through the reversed string word by word.
For each word you find, reverse that word individually. This puts the letters of each word back in the correct order, but keeps the words themselves in the reversed order.

Code Implementation

def reverse_words(list_of_characters):
    def reverse_substring(list_of_characters, start, end):
        while start < end:
            list_of_characters[start], list_of_characters[end] = list_of_characters[end], list_of_characters[start]
            start += 1
            end -= 1

    # Reverse the entire string to put words in reverse order
    reverse_substring(list_of_characters, 0, len(list_of_characters) - 1)

    start_index = 0
    for index in range(len(list_of_characters) + 1):
        if index == len(list_of_characters) or list_of_characters[index] == ' ':
            # Reverse each word to get letters in correct order
            reverse_substring(list_of_characters, start_index, index - 1)

            start_index = index + 1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Reverse the entire string of characters. So, if the original string was 'the sky is blue', it becomes 'eulb si yks eht'.
Now, go through the reversed string and reverse each word separately. In our example, 'eulb' becomes 'blue', 'si' becomes 'is', 'yks' becomes 'sky', and 'eht' becomes 'the'.
The final result after reversing each word is 'blue is sky the', which is the desired output.

Code Implementation

def reverse_words(list_of_characters):
    def reverse_range(list_to_reverse, start_index, end_index):
        while start_index < end_index:
            list_to_reverse[start_index], list_to_reverse[end_index] = list_to_reverse[end_index], list_to_reverse[start_index]
            start_index += 1
            end_index -= 1

    # First, reverse the entire string.
    reverse_range(list_of_characters, 0, len(list_of_characters) - 1)

    start_of_word_index = 0
    for index in range(len(list_of_characters) + 1):
        # Identify word boundaries using spaces
        if index == len(list_of_characters) or list_of_characters[index] == ' ':
            # Reverse each word individually.
            reverse_range(list_of_characters, start_of_word_index, index - 1)

            # Move the start index to the next word.
            start_of_word_index = index + 1

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return immediately or throw an IllegalArgumentException as appropriate for the language.
String with only spaces	Treat multiple spaces as single spaces, resulting in an empty or single-space string after reversal.
String with leading/trailing spaces	Trim leading and trailing spaces before reversing the words to avoid extra spaces in the output.
Single word string	The reversed string will be the same as the original string, so return the original.
String with consecutive multiple spaces between words	Reduce multiple spaces to single spaces during processing.
Maximum length string (memory constraints)	Ensure the solution doesn't exceed memory limits and potentially consider in-place reversal if memory is a concern.
String containing non-ASCII characters	Ensure the string reversal algorithm handles Unicode characters correctly, using UTF-8 encoding or similar.
Integer overflow when calculating lengths or indices	Use appropriate data types (e.g., long) or validate input lengths to prevent integer overflow.

Null or empty input string

How to Handle:

Return immediately or throw an IllegalArgumentException as appropriate for the language.

String with only spaces

How to Handle:

Treat multiple spaces as single spaces, resulting in an empty or single-space string after reversal.

String with leading/trailing spaces

How to Handle:

Trim leading and trailing spaces before reversing the words to avoid extra spaces in the output.

Single word string

How to Handle:

The reversed string will be the same as the original string, so return the original.

String with consecutive multiple spaces between words

How to Handle:

Reduce multiple spaces to single spaces during processing.

Maximum length string (memory constraints)

How to Handle:

Ensure the solution doesn't exceed memory limits and potentially consider in-place reversal if memory is a concern.

String containing non-ASCII characters

How to Handle:

Ensure the string reversal algorithm handles Unicode characters correctly, using UTF-8 encoding or similar.

Integer overflow when calculating lengths or indices

How to Handle:

Use appropriate data types (e.g., long) or validate input lengths to prevent integer overflow.