Given a Tic-Tac-Toe board as a string array board, return true if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.

The board is a 3 x 3 array that 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 three 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.


&nbsp;
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 = ["XOX","O O","XOX"]
Output: true


&nbsp;
Constraints:


	board.length == 3
	board[i].length == 3
	board[i][j] is either 'X', 'O', or ' '.


class Solution:
    def validTicTacToe(self, board: List[str]) -> bool:
                                            # The two criteria for a valid board are:
                                            #   1) num of Xs - num of Os is 0 or 1
                                            #   2) X is not a winner if the # of moves is even, and
                                            #      O is not a winner if the # of moves is odd.

        d = {'X': 1, 'O': -1, ' ': 0}               # transform the 1x3 str array to a 1x9 int array
        s = [d[ch] for ch in ''.join(board)]        # Ex: ["XOX"," X ","   "] --> [1,-1,1,0,1,0,0,0,0]
        sm = sum(s)

        if sm>>1: return False                                      # <-- criterion 1
        
        n = -3 if sm == 1 else 3                                    # <-- criterion 2.
        if n in {s[0]+s[1]+s[2], s[3]+s[4]+s[5], s[6]+s[7]+s[8], 
                 s[0]+s[3]+s[6], s[1]+s[4]+s[7], s[2]+s[5]+s[8],         # the elements of the set are 
                 s[0]+s[4]+s[8], s[2]+s[4]+s[6]}: return False           # the rows, cols, and diags
        
        return True                                                 # <-- both criteria are true
class Solution {
    public boolean validTicTacToe(String[] board) {
        //cnt number of X and O
        int x = cntNumber('X', board);
        //this check can be omitted, it can be covered in the second number check.
        if(x >5){
            return false;
        }
        int o = cntNumber('O', board);
        if(x < o || x > o + 1){
            return false;
        }
        //if(x <3 ) true, no need to see winning
        if(o >= 3){
            //if x has won, but game doesnt stop
            if(x == o && hasWon('X', board)){
                return false;
            }
            //if o has won, but game doesnt stop
            if( x > o && hasWon('O', board) ){
                return false;
            }
        }
        return true;
    }

    private int cntNumber(char target, String[] board){
        int res = 0;
        for(int i = 0; i<3; i++) {
            for(int j = 0; j<3; j++) {
                if(target == board[i].charAt(j)){
                    res++;
                }
            }
        }
        return res;
    }

    private boolean hasWon(char target, String[] board){
        String toWin = Character.toString(target).repeat(3);
        for(int i = 0; i<3; i++) {
            if(board[i].equals(toWin)){
                return true;
            }
        }
        for(int j = 0; j<3; j++) {
            boolean col = true;
            for(int i = 0; i<3; i++) {
                col = col && target == board[i].charAt(j);
                if(!col){
                    break;
                }
            }
            if(col){
                return true;
            }
        }
        //check diagonal. If center is not target, not possible to form diag win.
        if(target != board[1].charAt(1)){
            return false;
        }

        boolean diagonal1 = target == board[0].charAt(0);
        //only proceed if the first letter match. Otherwise might get false positive
        if(diagonal1){
            if(target == board[2].charAt(2)){
                return true;
            }
        }

        boolean diagonal2 = target == board[0].charAt(2);
        if(diagonal2){
            if(target == board[2].charAt(0)){
                return true;
            }
        }
        return false;
    }
}
class Solution {
public:
    
    bool win(vector<string> board, char player, int size){
        int row_win=0, col_win=0, diagonal_win=0, rev_diagonal_win=0;
        
        for(int i=0;i<3;i++){
            
            row_win=0; 
            col_win=0;
            
            for(int j=0;j<3;j++){
                
                if(player == board[i][j]){
                    row_win++; 
                    if(row_win == 3)
                        return 1;
                }
                
                if(player == board[j][i]){
                    col_win++;
                    if(col_win == 3)
                        return 1;
                }
                    
                if(i==j && player==board[i][j]){
                    diagonal_win++;
                }
                
                if(i+j == size-1 && player==board[i][j]){
                    rev_diagonal_win++;
                }
                    
            }
        }
        
        if(diagonal_win==3 || rev_diagonal_win==3)
            return 1;
        
        return 0;
    }
    
    bool validTicTacToe(vector<string>& board) {
        int count_x=0, count_o=0, size = board.size();
        for(auto i:board){
            for(auto j:i){
                if(j=='X') count_x++;
                else if(j=='O') count_o++;
            }
        }
        if(count_o>count_x || count_x-count_o>=2)
            return false;
        if(count_x>=3 && count_x==count_o && win(board, 'X', size))
            return false;
        if(count_o>=3 && count_x>count_o && win(board, 'O', size))
            return false;
        
        return true;
    }
};
var validTicTacToe = function(board) {
    let playerX = 0 , playerO = 0;
    let horizontal = [0,0,0];
    let vertical = [0,0,0];
    let diagnol = [0, 0];
    
    const transformConfig=(row,col,val)=>{
        horizontal[row] +=val; 
        vertical[col]+=val;
        if(row ===col ){
           diagnol[0]+=val; 
            if(row+col == board.length-1){
             diagnol[1]+=val; 
            }
        }else if(row+col == board.length-1){
             diagnol[1]+=val; 
        }
    }
    
    board.forEach((data,row)=>{
        data.split("").forEach((turn,col)=>{
            if(turn == 'X'){
                playerX++
                transformConfig(row,col,1)
            }else if(turn == 'O'){
                playerO++;
                transformConfig(row,col,-1);
            }
        });
    });
    if(playerX<playerO ||playerX-playerO>1 ) return false;
    if(horizontal.includes(3)&&playerX<= playerO)return false;
    if(vertical.includes(3)&&playerX <= playerO)return false;
    if(diagnol.includes(3)&&playerX <=playerO)return false;
    if(horizontal.includes(-3)&&playerX> playerO)return false;
    if(vertical.includes(-3)&&playerX> playerO)return false;
    if(diagnol.includes(-3)&&playerX>playerO)return false;
    
    return true;
};
Valid Tic-Tac-Toe State