I think it is easier if you rewrite your inequality as 
\begin{align} 
 & P( \bigcap_{i=1}^{s-1}A_i ) - P ( \bigcap_{i=1}^{s-1}A_i \cap A_s) \geq  P(\bigcap_{i=1}^{s-1}A_i)(1-P(A_s)) \\ 
 & \iff P(A_s) \geq P(A_s | \bigcap_{i=1}^{s-1}A_i).
\end{align}
Now let $\{X_i\}_{i=1}^n$ be Bernouli independent random variables with success probability $1/n$ and $N_{s-1}$ is the random variable which counts how many times the letters $\{1,\dots,s-1\}$ appear in a given random word. Then the LHS is exactly $$P(\sum_{i=1}^nX_i \geq p )$$ while the RHS is exactly 
$$ P(\sum_{i=1}^{n-N_{s-1}}X_i\geq p),$$
which is clearly smaller.