Problem Overview

You are given a string s that contains words separated by single spaces. Your task is to reverse the characters of each word, while keeping the order of the words and the spaces exactly the same.

In simple terms, you need to reverse each word individually, but not the order of the words.

Example 1:

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

Example 2:

Input: s = "God Ding"  
Output: "doG gniD"

---

Intuition / Approach

The problem focuses on reversing individual words rather than the whole sentence.

We can approach it as follows:

1. Split the string s into words using spaces as delimiters.
2. For each word, reverse its characters using a helper method or a simple two-pointer swap.
3. Combine all the reversed words back into a single string separated by spaces.

This approach ensures that:

• The order of the words remains the same.
• Each word’s internal characters are reversed efficiently.

---

Algorithm Explanation

1. Split the string s into an array of words using split(" ").
2. For each word in the array:
   • Convert it into a character array.
   • Reverse the array using a two-pointer approach.
3. Append the reversed word to a StringBuilder.
4. Add a space after each word except the last one.
5. Return the final combined string.

---

Java Code Implementation

public class ReverseWordsInAStringIII {

    public String reverseWords(String s) {
        String[] words = s.split(" ");
        StringBuilder result = new StringBuilder();

        for (int i = 0; i < words.length; i++) {
            result.append(reverseWord(words[i]));
            if (i < words.length - 1) {
                result.append(" ");
            }
        }

        return result.toString();
    }

    // Helper method to reverse a single word
    private String reverseWord(String word) {
        char[] arr = word.toCharArray();
        int left = 0, right = arr.length - 1;
        
        while (left < right) {
            char temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
        
        return new String(arr);
    }

    // Example usage
    public static void main(String[] args) {
        ReverseWordsInAStringIII solution = new ReverseWordsInAStringIII();
        String s = "Let's take LeetCode contest";
        System.out.println(solution.reverseWords(s));  
        // Output: "s'teL ekat edoCteeL tsetnoc"
    }
}

---

Complexity Analysis

Time Complexity:

• Each word is reversed in O(m) time, where m is the word length.
• Since all characters are processed exactly once, the total time complexity is O(n), where n is the total length of the string.

Space Complexity:

• A StringBuilder and a few helper variables are used, giving an overall O(n) space complexity for the output string.
• If we ignore the output, the extra space usage is O(1).

---

Alternative Approaches

1. In-Place Reversal Without Splitting:
   Instead of splitting, you can reverse each word directly while traversing the string character by character.
   • Use two pointers: one to find the start of a word and another to find its end.
   • Reverse the characters between them.
   • Move to the next word after the space.
     This avoids the need for creating a new array with split() and is slightly more memory efficient.
2. Using Built-in StringBuilder Reverse (Simpler but less educational):
   You can use new StringBuilder(word).reverse().toString() for each word.
   This simplifies the implementation but hides the core reversal logic.