Jobs

Interviews

Discussions

Reverse Words in a String III

Easy

Asked by:

More companies

92 views

Topics:

ArraysTwo PointersStrings

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⁴
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.

Try coding it in LeetCode

Reverse Words in a String III

Easy

Asked by:

92 views

Topics:

ArraysTwo PointersStrings

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⁴
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.

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:

Can the input string `s` contain leading or trailing spaces? Should I trim them or preserve them?
Can the input string `s` contain multiple spaces between words? If so, how should I handle them in the reversed string?
Is the input string `s` guaranteed to contain at least one word, or could it be empty?
Should I handle non-ASCII characters or special characters in the string, or can I assume it contains only standard English letters, spaces and punctuation?
Should the output string maintain the exact spacing as the input string, aside from the reversed words themselves?

Brute Force Solution

Approach

The goal is to reverse each word within a sentence while keeping the word order intact. The brute force method involves examining each word one at a time and performing the reversal operation directly. Afterwards, the reversed words are put back together.

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

First, we split the entire sentence into individual words.
Then, for each word, we take the letters and swap the first and last letters, then the second and second-to-last, and so on, until the whole word is reversed.
Finally, we put the reversed words back together in the same order they were in the original sentence, making sure to include spaces between them.

Code Implementation

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

    #Iterate through each word
    for word in words:
        word_characters = list(word)
        left_index = 0
        right_index = len(word_characters) - 1

        #Reverse the word using two pointers
        while left_index < right_index:
            word_characters[left_index], word_characters[right_index] = \
                word_characters[right_index], word_characters[left_index]
            left_index += 1
            right_index -= 1

        reversed_word = "".join(word_characters)
        reversed_words.append(reversed_word)

    #Join the reversed words with spaces
    return " ".join(reversed_words)

Big(O) Analysis

Time Complexity

O(n) – The algorithm first splits the input string of length n into words, which takes O(n) time. Then, it iterates through each word. Reversing a single word of length k takes O(k) time. Since the total length of all words is n, reversing all words takes O(n) time. Finally, joining the reversed words back together 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 primary space complexity arises from splitting the input string into an array of words. In the worst-case scenario, where the input string contains distinct words separated by spaces, the resulting array will have a size proportional to the length of the input string (N). Additionally, reversing each word might involve creating a temporary copy of the word as a list of characters, which, in aggregate across all words, can also approach O(N) in the worst case (e.g., a single long word). Therefore, the auxiliary space used grows linearly with the input size N, leading to a space complexity of O(N).

Optimal Solution

Approach

The main idea is to process each word in the given string individually. We'll go through each word, reverse it, and then put the reversed word back into a new string with spaces in the correct places.

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

First, split the entire string into individual words.
Then, take each word, one at a time, and reverse the letters within that word.
After reversing a word, add it to a new string that will hold the result.
Put a space after each reversed word to separate it from the next, except for the very last word.
Finally, return the new string containing all the reversed words with spaces.

Code Implementation

def reverse_words_in_string(input_string):
    list_of_words = input_string.split()
    reversed_string = ""

    for i in range(len(list_of_words)):
        # Reverse each word individually.
        reversed_word = list_of_words[i][::-1]

        reversed_string += reversed_word

        # Avoid adding space after the last word.
        if i < len(list_of_words) - 1:
            reversed_string += " "

    return reversed_string

def main():
    input_string = "Let's take LeetCode contest"
    # Demonstrates the function with a sample input.
    result = reverse_words_in_string(input_string)
    print(result)

if __name__ == "__main__":
    main()

Big(O) Analysis

Time Complexity

O(n) – The algorithm first splits the string of length n into words. Splitting takes O(n) time. Then, for each word, the algorithm reverses it. Reversing each word also takes a linear time relative to the length of the word. Because the total length of all the words equals n (the length of the input string), the time spent reversing all words is O(n). Finally, joining the reversed words together into the output 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 algorithm splits the input string into an array of words. This array can, in the worst case, contain N words, where N is the length of the input string. Additionally, a new string to store the reversed words is created, which, in the worst case, can also have a length of N (e.g., when each word is of length one). Therefore, the space complexity is proportional to the input string's length, resulting in O(N).

Edge Cases

Case	How to Handle
Null or Empty Input String	Return an empty string or throw an IllegalArgumentException as appropriate for the use case.
String with only whitespace	Should return the same string, preserving the whitespace only string without reversing anything.
String with leading and trailing whitespace	Whitespace should be preserved at the beginning and end; reverse each word individually, then stitch it back.
String with consecutive whitespace characters between words	The solution must handle consecutive whitespace correctly by preserving the multiple spaces and only reversing the words separated by them.
String containing only one word	Reverse the characters of the single word and return it, preserving any surrounding whitespace.
String with very long words (close to maximum string size)	Ensure that reversing very long words does not cause memory issues or stack overflow if recursion is used and test performance to see if improvements could be made.
String containing non-ASCII characters (Unicode)	Ensure that character reversal handles Unicode characters correctly, as some languages have multi-byte character encodings.
String with special characters (e.g., punctuation, symbols)	Treat special characters the same way as regular alphanumeric characters, reversing them within their words.

Null or Empty Input String

How to Handle:

Return an empty string or throw an IllegalArgumentException as appropriate for the use case.

String with only whitespace

How to Handle:

Should return the same string, preserving the whitespace only string without reversing anything.

String with leading and trailing whitespace

How to Handle:

Whitespace should be preserved at the beginning and end; reverse each word individually, then stitch it back.

String with consecutive whitespace characters between words

How to Handle:

The solution must handle consecutive whitespace correctly by preserving the multiple spaces and only reversing the words separated by them.

String containing only one word

How to Handle:

Reverse the characters of the single word and return it, preserving any surrounding whitespace.

String with very long words (close to maximum string size)

How to Handle:

Ensure that reversing very long words does not cause memory issues or stack overflow if recursion is used and test performance to see if improvements could be made.

String containing non-ASCII characters (Unicode)

How to Handle:

Ensure that character reversal handles Unicode characters correctly, as some languages have multi-byte character encodings.

String with special characters (e.g., punctuation, symbols)

How to Handle:

Treat special characters the same way as regular alphanumeric characters, reversing them within their words.

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:

Can the input string `s` contain leading or trailing spaces? Should I trim them or preserve them?
Can the input string `s` contain multiple spaces between words? If so, how should I handle them in the reversed string?
Is the input string `s` guaranteed to contain at least one word, or could it be empty?
Should I handle non-ASCII characters or special characters in the string, or can I assume it contains only standard English letters, spaces and punctuation?
Should the output string maintain the exact spacing as the input string, aside from the reversed words themselves?

Brute Force Solution

Approach

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

First, we split the entire sentence into individual words.
Then, for each word, we take the letters and swap the first and last letters, then the second and second-to-last, and so on, until the whole word is reversed.
Finally, we put the reversed words back together in the same order they were in the original sentence, making sure to include spaces between them.

Code Implementation

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

    #Iterate through each word
    for word in words:
        word_characters = list(word)
        left_index = 0
        right_index = len(word_characters) - 1

        #Reverse the word using two pointers
        while left_index < right_index:
            word_characters[left_index], word_characters[right_index] = \
                word_characters[right_index], word_characters[left_index]
            left_index += 1
            right_index -= 1

        reversed_word = "".join(word_characters)
        reversed_words.append(reversed_word)

    #Join the reversed words with spaces
    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, split the entire string into individual words.
Then, take each word, one at a time, and reverse the letters within that word.
After reversing a word, add it to a new string that will hold the result.
Put a space after each reversed word to separate it from the next, except for the very last word.
Finally, return the new string containing all the reversed words with spaces.

Code Implementation

def reverse_words_in_string(input_string):
    list_of_words = input_string.split()
    reversed_string = ""

    for i in range(len(list_of_words)):
        # Reverse each word individually.
        reversed_word = list_of_words[i][::-1]

        reversed_string += reversed_word

        # Avoid adding space after the last word.
        if i < len(list_of_words) - 1:
            reversed_string += " "

    return reversed_string

def main():
    input_string = "Let's take LeetCode contest"
    # Demonstrates the function with a sample input.
    result = reverse_words_in_string(input_string)
    print(result)

if __name__ == "__main__":
    main()

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or Empty Input String	Return an empty string or throw an IllegalArgumentException as appropriate for the use case.
String with only whitespace	Should return the same string, preserving the whitespace only string without reversing anything.
String with leading and trailing whitespace	Whitespace should be preserved at the beginning and end; reverse each word individually, then stitch it back.
String with consecutive whitespace characters between words	The solution must handle consecutive whitespace correctly by preserving the multiple spaces and only reversing the words separated by them.
String containing only one word	Reverse the characters of the single word and return it, preserving any surrounding whitespace.
String with very long words (close to maximum string size)	Ensure that reversing very long words does not cause memory issues or stack overflow if recursion is used and test performance to see if improvements could be made.
String containing non-ASCII characters (Unicode)	Ensure that character reversal handles Unicode characters correctly, as some languages have multi-byte character encodings.
String with special characters (e.g., punctuation, symbols)	Treat special characters the same way as regular alphanumeric characters, reversing them within their words.

Null or Empty Input String

How to Handle:

Return an empty string or throw an IllegalArgumentException as appropriate for the use case.

String with only whitespace

How to Handle:

Should return the same string, preserving the whitespace only string without reversing anything.

String with leading and trailing whitespace

How to Handle:

Whitespace should be preserved at the beginning and end; reverse each word individually, then stitch it back.

String with consecutive whitespace characters between words

How to Handle:

The solution must handle consecutive whitespace correctly by preserving the multiple spaces and only reversing the words separated by them.

String containing only one word

How to Handle:

Reverse the characters of the single word and return it, preserving any surrounding whitespace.

String with very long words (close to maximum string size)

How to Handle:

Ensure that reversing very long words does not cause memory issues or stack overflow if recursion is used and test performance to see if improvements could be made.

String containing non-ASCII characters (Unicode)

How to Handle:

Ensure that character reversal handles Unicode characters correctly, as some languages have multi-byte character encodings.

String with special characters (e.g., punctuation, symbols)

How to Handle:

Treat special characters the same way as regular alphanumeric characters, reversing them within their words.