Smallest length such that all substrings of that length contain at least 1 common character

Question

Given a string, I have to return the smallest possible value of $k$ such that all of its sub-strings of length $k$ have at least one common character. Each sub-string must have the same common character.

Examples:

1. y d c b f

Answer = $3$ (common character is 'c')

2. n n n n n n n n n

Answer = $1$ (common character is 'n')

3. y e y d y e y

Answer = $2$ (common character is 'y')

The only solution I have thought of till now goes like this:

Find all sub-strings of length $x$ from $1$ through $n-1$ (where $n$ is the length of the given string). Compare the sub-string for common characters (and store which characters are common). As soon as I come across a pair of the sub-string of length $x$ which doesn't have any common characters I move to the next value of $x$. If no such $x$ is found, return $n$.

Is a more efficient solution possible?