Over the alphabet {a,b,c,d}, how would i construct a NFA that only accepts strings that end with a letter that is already part of the string?
The idea is to implement the following regular expression:
$$
\sum_{\sigma \in \Sigma} \Sigma^* \sigma \Sigma^* \sigma.
$$
Details left to you. Number of states is $|\Sigma| + 2$.

Let us show that $|\Sigma| + 2$ is the optimal number of states, using the fooling set method. We have to give $|\Sigma|+2$ pairs $(x_i,y_i)$ such that $x_iy_i \in L$ (here $L$ is your language), but for each $i \neq j$, either $x_iy_j \notin L$ or $x_jy_i \notin L$. For each $\sigma$, we have the pair $x_\sigma = y_\sigma = \sigma$. For some arbitrary $\tau \in \Sigma$, we have the two pairs $x_\gets = \tau\tau, y_\gets = \epsilon$ and $x_\to = \epsilon,y_\to = \tau\tau$. You can check that indeed $x_iy_i \in L$ for all $i$. In the other direction:


If $\sigma_1 \neq \sigma_2 \in \Sigma$ then $x_{\sigma_1} y_{\sigma_2} \notin L$.
If $\sigma \in \Sigma$ then $x_\sigma y_\gets, x_\to y_\sigma \notin L$.
Similarly, $x_\to y_\gets \notin L$.