class Solution {
    public String reverseString(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }

        int left = 0;
        int right = s.length() - 1;
        char[] arr = s.toCharArray();
        // string reverse
        while(left <= right) {
            char temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
        return new String(arr);

    }
}

public class Solution {
    public String reverseWords(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }


        int left = 0;
        int right = s.length() - 1;
        char[] arr = s.toCharArray();

        // reverse the whole sentense

        swap(arr, left, right);


        System.out.println(new String(arr));
        // reduce the multiple space to singe space between words
        int slow = 0;
        for (int fast = 0; fast < arr.length; fast++){
            if(arr[fast] == ' ' && (fast == 0 || arr[fast - 1] == ' ')) {
                continue;
            }
            arr[slow++] = arr[fast];
        }

        int end = 0;
        if (slow > 0 && arr[slow - 1] == ' ') {
            end = slow - 1;
        } else {
            end = slow;
        }
        //reverse each word

        int i = 0;
        while(i < end) {
            int start = i;
            while(i < end && arr[i] != ' ') {
                i++;
            }
            if (start < end && i - 1 < end) {
                swap(arr, start, i - 1);
            }
            i++;
        }

        return new String(arr, 0, end);
    }

    private void swap(char[] arr, int left, int right) {
        while(left <= right) {
            char temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
}