A Tic-Tac-Toe board is given as a string arrayboard. Return True if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.

Theboardis a 3 x 3 array, and consists of characters" ","X", and"O". The " " character represents an empty square.

Here are the rules of Tic-Tac-Toe:

• Players take turns placing characters into empty squares (" ").
• The first player always places "X" characters, while the second player always places "O" characters.
• "X" and "O" characters are always placed into empty squares, never filled ones.
• The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
• The game also ends if all squares are non-empty.
• No more moves can be played if the game is over.

Example 1:
Input:
 board = ["O  ", "   ", "   "]

Output:
 false

Explanation:
 The first player always plays "X".


Example 2:
Input:
 board = ["XOX", " X ", "   "]

Output:
 false

Explanation:
 Players take turns making moves.


Example 3:
Input:
 board = ["XXX", "   ", "OOO"]

Output:
 false


Example 4:
Input:
 board = ["XOX", "O O", "XOX"]

Output:
 true

Note:

• board is a length-3 array of strings, where each string board[i] has length 3.
• Each board[i][j] is a character in the set {" ", "X", "O"} .

class Solution {
    public boolean validTicTacToe(String[] board) {
        int countX = getCount(board, 'X');
        int countO = getCount(board, 'O');

        if (countX != countO && countX != countO + 1) return false;
        if (checkWin(board, 'X') && countX != countO + 1) return false;
        if (checkWin(board, 'O') && countO != countX) return false;

        return true;
    }

    private int getCount(String[] board, Character c){
        int count = 0;

        for (int i = 0; i < 3; i++){
            for (int j = 0; j < 3; j++){
                if (board[i].charAt(j) == c) count++;
            }
        }

        return count;
    }

    private boolean checkWin(String[] board, Character s){

        // row
        for (int i = 0; i < 3; i++){
            int count = 0;
            for (int j = 0; j < 3; j++){
                if (board[i].charAt(j) == s) count++;
            }

            //System.out.println("s: " + s + " count: " + count);
            if (count == 3) return true;
        }

        // col
        for (int j = 0; j < 3; j++){
            int count = 0;
            for (int i = 0; i < 3; i++){
                if (board[i].charAt(j) == s) count++;
            }

            if (count == 3) return true;
        }

        // top-left to bottom-right
        if (board[0].charAt(0) == s && board[1].charAt(1) == s && board[2].charAt(2) == s) return true;

        // top-right to bottom-left
        if (board[0].charAt(2) == s && board[1].charAt(1) == s && board[2].charAt(0) == s) return true;

        return false;
    }
}