  The deviation of the observed frequency of a word $w$ from its expected
frequency in a given sequence $x$ is used to determine whether or not the word
is avoided. This concept is particularly useful in DNA linguistic analysis. The
value of the standard deviation of $w$, denoted by $std(w)$, effectively
characterises the extent of a word by its edge contrast in the context in which
it occurs. A word $w$ of length $k>2$ is a $\rho$-avoided word in $x$ if
$std(w) \leq \rho$, for a given threshold $\rho < 0$. Notice that such a word
may be completely absent from $x$. Hence computing all such words na\"{\i}vely
can be a very time-consuming procedure, in particular for large $k$. In this
article, we propose an $O(n)$-time and $O(n)$-space algorithm to compute all
$\rho$-avoided words of length $k$ in a given sequence $x$ of length $n$ over a
fixed-sized alphabet. We also present a time-optimal $O(\sigma n)$-time and
$O(\sigma n)$-space algorithm to compute all $\rho$-avoided words (of any
length) in a sequence of length $n$ over an alphabet of size $\sigma$.
Furthermore, we provide a tight asymptotic upper bound for the number of
$\rho$-avoided words and the expected length of the longest one. We make
available an open-source implementation of our algorithm. Experimental results,
using both real and synthetic data, show the efficiency of our implementation.
