EGMO 2023 Problem 3

Let $k$ be a positive integer. Lexi has a dictionary $\mathcal{D}$ consisting of some $k$-letter strings containing only the letters $A$ and $B$. Lexi would like to write either the letter $A$ or the letter $B$ in each cell of a $k \times k$ grid so that each column contains a string from $\mathcal{D}$ when read from top-to-bottom and each row contains a string from $\mathcal{D}$ when read from left-to-right.

What is the smallest integer $m$ such that if $\mathcal{D}$ contains at least $m$ different strings, then Lexi can fill her grid in this manner, no matter what strings are in $\mathcal{D}$ ?