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

<p>The board is a <code>3 x 3</code> array that consists of characters <code>&#39; &#39;</code>, <code>&#39;X&#39;</code>, and <code>&#39;O&#39;</code>. The <code>&#39; &#39;</code> character represents an empty square.</p>

<p>Here are the rules of Tic-Tac-Toe:</p>

<ul>
	<li>Players take turns placing characters into empty squares <code>&#39; &#39;</code>.</li>
	<li>The first player always places <code>&#39;X&#39;</code> characters, while the second player always places <code>&#39;O&#39;</code> characters.</li>
	<li><code>&#39;X&#39;</code> and <code>&#39;O&#39;</code> characters are always placed into empty squares, never filled ones.</li>
	<li>The game ends when there are three of the same (non-empty) character filling any row, column, or diagonal.</li>
	<li>The game also ends if all squares are non-empty.</li>
	<li>No more moves can be played if the game is over.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/15/tictactoe1-grid.jpg" style="width: 253px; height: 253px;" />
<pre>
<strong>Input:</strong> board = [&quot;O  &quot;,&quot;   &quot;,&quot;   &quot;]
<strong>Output:</strong> false
<strong>Explanation:</strong> The first player always plays &quot;X&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/15/tictactoe2-grid.jpg" style="width: 253px; height: 253px;" />
<pre>
<strong>Input:</strong> board = [&quot;XOX&quot;,&quot; X &quot;,&quot;   &quot;]
<strong>Output:</strong> false
<strong>Explanation:</strong> Players take turns making moves.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/15/tictactoe4-grid.jpg" style="width: 253px; height: 253px;" />
<pre>
<strong>Input:</strong> board = [&quot;XOX&quot;,&quot;O O&quot;,&quot;XOX&quot;]
<strong>Output:</strong> true
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>board.length == 3</code></li>
	<li><code>board[i].length == 3</code></li>
	<li><code>board[i][j]</code> is either <code>&#39;X&#39;</code>, <code>&#39;O&#39;</code>, or <code>&#39; &#39;</code>.</li>
</ul>

class Solution:
    def validTicTacToe(self, board: List[str]) -> bool:
        # 1. Number of Xs must be equal to or greater than the number of Os
        # 2. Number of Xs must be at most one more than the number of Os
        # 3. if X wins then O does not win and the number of Xs is one greater than the number of Os
        # 4. if O wins then X does not win and the number of Os is equal to the number of Xs
        
        # Check the number of Xs
        # Check the number of Os
        # Check horizontals, verticals, and diagonals for Xs
        # Check horizontals, verticals, and diagonals for Os

        # if X wins:
            # return O does not win and the number of Xs is exactly one greater than the number of Os
        # else if O wins:
            # return X does not win and the number of Os is exactly equalt to the nnumber of Xs
        # else:
            # return the number of Xs is at most one greater than the number of Os

        row, col = len(board), len(board[0])
        x_count, o_count = 0, 0

        for i in range(row):
            for j in range(col):
                if board[i][j] == 'X':
                    x_count += 1
                elif board[i][j] == 'O':
                    o_count += 1

        if x_count < o_count or x_count > o_count + 1:
            return False

        def winner(board: List[str], player: str) -> bool:
            # Check rows, columns, and diagonals for a win
            for i in range(3):
                # Check rows
                if board[i][0] == board[i][1] == board[i][2] == player:
                    return True
                # Check columns
                if board[0][i] == board[1][i] == board[2][i] == player:
                    return True
            # Check diagonals
            if board[0][0] == board[1][1] == board[2][2] == player:
                return True
            if board[0][2] == board[1][1] == board[2][0] == player:
                return True
            return False

        # Check if X or O wins
        x_wins = winner(board, 'X')
        o_wins = winner(board, 'O')

        # 2. If X wins, O cannot win, and the number of Xs must be exactly one more than Os
        if x_wins and (o_wins or x_count != o_count + 1):
            return False

        # 3. If O wins, X cannot win, and the number of Xs must be equal to the number of Os
        if o_wins and (x_wins or x_count != o_count):
            return False

        # If none of the invalid conditions are met, the board is valid
        return True


31