# find max number of connected colors

grid = [
    ['green', 'green', 'blue', 'red'],
    ['green', 'blue', 'red', 'blue'],
    ['red', 'blue', 'blue', 'blue'],
    ['red', 'red', 'red', 'red'],
    ['red', 'red', 'red', 'red'],
]


def find_max_connected_colors(grid):
    """
    for each element
        check 4 spots (up down left right) (if they exist)
        if the color matches, increase the count for this connected component (or just save the connected component)

        basically, just get the connected component and length, and set the max length and color
    """
    seen = set()

    def get_neighbors(grid, position, color, max_x, max_y):
        x, y = position
        neighbors = []
        # right
        if x + 1 < max_x and grid[x + 1][y] == color:
            neighbors.append((x + 1, y))

        # left
        if x - 1 >= 0 and grid[x - 1][y] == color:
            neighbors.append((x - 1, y))

        # up
        if y + 1 < max_y and grid[x][y + 1] == color:
            neighbors.append((x, y + 1))

        # up
        if y - 1 >= 0 and grid[x][y - 1] == color:
            neighbors.append((x, y - 1))
        return neighbors

    max_x = len(grid)
    max_y = len(grid[0])

    max_count = 0
    max_color = None
    for i, row in enumerate(grid):
        for j, element in enumerate(row):
            if (i, j) not in seen:
                # find the connected component
                seen.add((i, j))
                stack = [(i, j)]
                count = 1
                while stack:
                    x, y = curr = stack.pop()
                    color = grid[x][y]
                    neighbors = get_neighbors(grid, curr, color, max_x, max_y)
                    for neighbor in neighbors:
                        if neighbor not in seen:
                            seen.add(neighbor)
                            stack.append(neighbor)
                            count += 1
                if count > max_count:
                    max_count = count
                    max_color = color
    return max_color, max_count