'''
keys: 
Solutions:
Similar:
T:
S:
'''
from typing import List
# reach the position means at the beginning the game board is empty
# then determine whether the given board is a valid status during the game

class Solution:
    def validTicTacToe(self, board: List[str]) -> bool:
        first, second = 'XO' # i.e., first = "X"
        x_count = sum(row.count(first) for row in board)
        o_count = sum(row.count(second) for row in board)

        def win(board, player):
            for i in range(3):
                # check each row
                if all(board[i][j] == player for j in range(3)):
                    return True
                # check each column
                if all(board[j][i] == player for j in range(3)):
                    return True
            # check diagonal
            return (player == board[0][0] == board[1][1] == board[2][2] or
                    player == board[1][1] == board[0][2] == board[2][0])

        if o_count not in {x_count-1, x_count}: 
            return False
        # first player win, i.e., one more "X" than "O"
        if win(board, first) and x_count-1 != o_count: 
            return False
        # second player win, i.e., "O" equal to "X"
        if win(board, second) and x_count != o_count: 
            return False

        return True