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 the random variables which indicate if the $i-th$ letter is $s$ or not. (Bernouli independent random variables with success probability $1/k$) Let also $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 smaller than
$$ P(\sum_{i=1}^{n-N_{s-1}}X_i\geq p| N_{s-1}\geq (s-1)p),$$
which is clearly smaller.