Constraints

• board always contains exactly 3 strings, each of length 3
• Each character is one of 'X', 'O', or '.'
• X always moves first, and players strictly alternate turns
• The game stops immediately after the first winning line is created

Examples

Solution

def solution(board):
    x_count = sum(row.count('X') for row in board)
    o_count = sum(row.count('O') for row in board)

    # X starts, so valid move counts are either equal or X has one extra move.
    if not (x_count == o_count or x_count == o_count + 1):
        return 'invalid'

    lines = []
    for i in range(3):
        lines.append([board[i][0], board[i][1], board[i][2]])
        lines.append([board[0][i], board[1][i], board[2][i]])
    lines.append([board[0][0], board[1][1], board[2][2]])
    lines.append([board[0][2], board[1][1], board[2][0]])

    def wins(player):
        return any(all(cell == player for cell in line) for line in lines)

    x_win = wins('X')
    o_win = wins('O')

    # Both players winning is impossible in a valid game.
    if x_win and o_win:
        return 'invalid'

    # If X wins, X must have moved last.
    if x_win:
        return 'X_wins' if x_count == o_count + 1 else 'invalid'

    # If O wins, O must have moved last.
    if o_win:
        return 'O_wins' if x_count == o_count else 'invalid'

    # No winner.
    if x_count + o_count == 9:
        return 'draw'

    return 'X_turn' if x_count == o_count else 'O_turn'

Time complexity: O(1). Space complexity: O(1).

Hints

1. Start by counting how many X's and O's are on the board. Only two count relationships are ever possible in a valid game.
2. Check all 8 possible winning lines. If X wins, X must have exactly one more move than O. If O wins, the counts must be equal.