Domain 1EasyCORE

Reverse Words in a String III

The problem requires reversing the order of characters in each word within a given string while maintaining the original order of the words and preserving whitespace. The input is a single string `s` containing printable ASCII characters, with no leading or trailing spaces and at least one word. Words are separated by a single space.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String

557. Reverse Words in a String III

Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 72.4%


Problem Breakdown

The problem requires reversing the order of characters in each word within a given string while maintaining the original order of the words and preserving whitespace. The input is a single string s containing printable ASCII characters, with no leading or trailing spaces and at least one word. Words are separated by a single space.

Inputs:

  • A string s.

Outputs:

  • A new string where each word’s characters are reversed but the order of words remains unchanged.

Implicit Constraints:

  • The string does not contain any leading or trailing spaces.
  • There is at least one word in the string.
  • Words are separated by a single space.

Intuition

A brute-force approach would involve splitting the string into words, reversing each word individually, and then joining them back together. This approach works but has a time complexity of O(n^2) due to the repeated reversal operations on substrings.

The key insight is to recognize that we can reverse the entire string first and then reverse each word in place to restore the correct order of words while reversing their characters. This reduces the time complexity to O(n).

Approach

  1. Reverse the Entire String: Start by reversing all characters in the string. This will put the words in reverse order but also reverse the characters within each word.
  2. Reverse Each Word in Place: Iterate through the reversed string and reverse each word individually. This step restores the correct order of words while keeping their characters reversed.

Data Structures:

  • Use a list to store the characters of the string for easy manipulation, as strings are immutable in Python.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the string. Reversing the entire string and then reversing each word takes linear time.
  • Space Complexity: O(n), due to the additional space used by the list to store the characters of the string.

Solution

def reverseWords(s: str) -> str:
    # Convert the string to a list of characters for easy manipulation
    chars = list(s)
    
    # Helper function to reverse a portion of the list in place
    def reverse(start, end):
        while start < end:
            chars[start], chars[end] = chars[end], chars[start]
            start += 1
            end -= 1
    
    # Step 1: Reverse the entire string
    reverse(0, len(chars) - 1)
    
    # Step 2: Reverse each word in place
    start = 0
    for end in range(len(chars)):
        if chars[end] == ' ':
            reverse(start, end - 1)
            start = end + 1
    # Reverse the last word (since there's no space after it)
    reverse(start, len(chars) - 1)
    
    # Convert the list of characters back to a string and return
    return ''.join(chars)

Edge Cases Handled

  • Single Word: If the input string contains only one word, the algorithm will correctly reverse that word.
  • Multiple Words: The algorithm handles strings with multiple words, reversing each word individually while maintaining their order.
  • No Spaces Between Words: Although the problem guarantees a single space between words, this approach naturally handles any number of spaces by treating consecutive spaces as delimiters.