package com.geth1b.coding.skills.lc;

/**
 *  [Reference URL]:  https://leetcode.com/problems/reverse-words-in-a-string-ii/
 *      [Algorithm]:  Two pointers sliding window
 * [Data Structure]:  Array / String
 *      [Time BigO]:  O(n)
 *     [Space BigO]:  O(1)
 *
 * @author geth1b
 */
public class _186_ReverseWordsInStringII {

  // Reverse words one by one; then reverse entire string once again
  // Use two pointers to handle each single word
  //
  // O(n) time
  // O(1) space
    
  public void reverseWords(char[] s) {
    int n = s.length;
    for (int i = 0, j = 0; j <= n; j++) { // include n to make code concise
      if (j == n || s[j] == ' ') {
        reverse(s, i, j - 1); // reverse one word; both indices are inclusive
        i = j + 1; // j will auto-increment in next for loop
      }
    }
    reverse(s, 0, n - 1);
  }

  private void reverse(char[] s, int L, int R) {
    while (L < R) {
      swap(s, L++, R--);
    }
  }

  private void swap(char[] s, int i, int j) {
    char tmp = s[i];
    s[i] = s[j];
    s[j] = tmp;
  }
}
