Jobs

Interviews

Discussions

Reverse Words in a String III

Easy

Google

2 views

Topics:

Strings

Given a string s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Example 1:

Input: s = "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

Example 2:

Input: s = "Mr Ding"
Output: "rM gniD"

Constraints:

1 <= s.length <= 5 * 10^4
s contains printable ASCII characters.
s does not contain any leading or trailing spaces.
There is at least one word in s.
All the words in s are separated by a single space.

Reverse Words in a String III

Easy

Google

2 views

Topics:

Strings

Given a string s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Example 1:

Input: s = "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

Example 2:

Input: s = "Mr Ding"
Output: "rM gniD"

Constraints:

1 <= s.length <= 5 * 10^4
s contains printable ASCII characters.
s does not contain any leading or trailing spaces.
There is at least one word in s.
All the words in s are separated by a single space.

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:

What characters can the input string `s` contain, and are there any non-alphanumeric characters I should consider?
Can the input string `s` contain leading or trailing spaces, and how should I handle them?
Can the input string `s` be empty or null, and if so, what should the expected output be?
Is the definition of a 'word' simply a sequence of non-space characters, or are there other delimiters to consider?
Should the output string maintain the original spacing and word order, only reversing the characters within each word?

Brute Force Solution

Approach

The brute force approach for reversing words in a string individually involves splitting the main string into separate words first. Then, for each word, we completely reverse the order of its letters before putting the reversed words back together into a new string.

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

First, we break up the big string into individual words, treating each space as the divider.
Next, we pick the very first word.
Now, for this first word, we flip it around so the last letter becomes the first, and so on until all letters are reversed.
Then we grab the next word from the original string.
We do the same thing: flip it around completely.
We keep doing this for every single word in the original string, reversing each one.
Finally, we take all these reversed words and string them back together in the same order they originally appeared, separated by spaces, to make the final reversed string.

Code Implementation

def reverse_words_in_string(input_string):
    words = input_string.split()
    reversed_words = []

    # Iterate through each word in the list of words
    for word in words:
        reversed_word = ''
        # Reverse the characters in the current word
        for i in range(len(word) - 1, -1, -1):
            reversed_word += word[i]
        reversed_words.append(reversed_word)

    # Join the reversed words back into a string
    return ' '.join(reversed_words)

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of length n (where n is the number of characters) to split it into words, which takes O(n) time. Then, for each word, it reverses the characters within that word. While technically there is a loop to reverse each word, the total number of characters across all words is still n. Therefore, reversing all the words takes a total of O(n) time. Finally, joining the reversed words back together takes O(n) time. Thus, the overall time complexity is O(n) + O(n) + O(n), which simplifies to O(n).

Space Complexity

O(N) – The brute force approach described involves splitting the input string into individual words. In the worst-case scenario, the input string contains only one word, which requires storing the entire string in a temporary list during the split operation. Reversing each word is done in place if a character array is used for each word. However, storing the split words results in an auxiliary data structure (a list of strings) that, in the worst case, holds 'N' characters (where N is the length of the input string). Therefore, the space complexity is O(N).

Optimal Solution

Approach

The goal is to reverse each word in a given sentence, while keeping the original order of the words. The efficient approach is to split the sentence into individual words, reverse each word separately, and then combine them back together. This avoids unnecessary operations and directly addresses the problem's core requirement.

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

First, take the entire sentence and separate it into individual words.
For each word that you separated, reverse the order of the characters within that word.
Finally, put all the reversed words back together in their original sequence, making sure to add spaces between them to form the final reversed sentence.

Code Implementation

def reverse_words_in_string(input_string):
    words = input_string.split()

    reversed_words = []
    for word in words:
        # Reverse each word to meet problem requirements.
        reversed_word = word[::-1]
        reversed_words.append(reversed_word)

    # Rejoin the reversed words into a single string
    return ' '.join(reversed_words)

Big(O) Analysis

Time Complexity

O(n) – The solution first splits the string into words, which takes O(n) time where n is the length of the string. Then, each word is reversed. Reversing each word is proportional to the length of that word. Summing the lengths of all words equals the total length of the string, which is n. Combining the reversed words back into a string also takes O(n) time. Therefore, the overall time complexity is O(n) + O(n) + O(n), which simplifies to O(n).

Space Complexity

O(N) – The space complexity is O(N) because the algorithm splits the input sentence into individual words, creating a list of these words. In the worst case, where the input sentence contains only one very long word, the list of words will have a size of N, where N is the length of the input string. Reversing each word in place does not contribute significantly to space complexity. Finally, joining the reversed words back into a string creates another string that could be of length N. Thus, the dominant factor for space usage is the list of words, which takes O(N) space.

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string or null depending on the requirements since there are no words to reverse.
String with leading/trailing spaces	Trim leading and trailing spaces before processing to avoid incorrect word boundaries.
String with multiple spaces between words	Normalize spaces to single spaces between words before reversing to ensure correct word separation.
String containing only spaces	Return an empty string after trimming since there are no actual words to reverse.
String with a single word	Return the single word itself since reversing its words has no effect.
String with special characters or non-alphanumeric characters	Handle these characters as part of the word to reverse, unless specifically excluded by the problem.
Maximum string length (memory constraints)	Consider using an in-place reversal algorithm if memory usage is a critical concern.
String with very long words	Ensure the reversal algorithm handles very long words efficiently without causing performance issues.

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:

What characters can the input string `s` contain, and are there any non-alphanumeric characters I should consider?
Can the input string `s` contain leading or trailing spaces, and how should I handle them?
Can the input string `s` be empty or null, and if so, what should the expected output be?
Is the definition of a 'word' simply a sequence of non-space characters, or are there other delimiters to consider?
Should the output string maintain the original spacing and word order, only reversing the characters within each word?

Brute Force Solution

Approach

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

First, we break up the big string into individual words, treating each space as the divider.
Next, we pick the very first word.
Now, for this first word, we flip it around so the last letter becomes the first, and so on until all letters are reversed.
Then we grab the next word from the original string.
We do the same thing: flip it around completely.
We keep doing this for every single word in the original string, reversing each one.
Finally, we take all these reversed words and string them back together in the same order they originally appeared, separated by spaces, to make the final reversed string.

Code Implementation

def reverse_words_in_string(input_string):
    words = input_string.split()
    reversed_words = []

    # Iterate through each word in the list of words
    for word in words:
        reversed_word = ''
        # Reverse the characters in the current word
        for i in range(len(word) - 1, -1, -1):
            reversed_word += word[i]
        reversed_words.append(reversed_word)

    # Join the reversed words back into a string
    return ' '.join(reversed_words)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, take the entire sentence and separate it into individual words.
For each word that you separated, reverse the order of the characters within that word.
Finally, put all the reversed words back together in their original sequence, making sure to add spaces between them to form the final reversed sentence.

Code Implementation

def reverse_words_in_string(input_string):
    words = input_string.split()

    reversed_words = []
    for word in words:
        # Reverse each word to meet problem requirements.
        reversed_word = word[::-1]
        reversed_words.append(reversed_word)

    # Rejoin the reversed words into a single string
    return ' '.join(reversed_words)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string or null depending on the requirements since there are no words to reverse.
String with leading/trailing spaces	Trim leading and trailing spaces before processing to avoid incorrect word boundaries.
String with multiple spaces between words	Normalize spaces to single spaces between words before reversing to ensure correct word separation.
String containing only spaces	Return an empty string after trimming since there are no actual words to reverse.
String with a single word	Return the single word itself since reversing its words has no effect.
String with special characters or non-alphanumeric characters	Handle these characters as part of the word to reverse, unless specifically excluded by the problem.
Maximum string length (memory constraints)	Consider using an in-place reversal algorithm if memory usage is a critical concern.
String with very long words	Ensure the reversal algorithm handles very long words efficiently without causing performance issues.