Suppose the alphabet is {a,b}. I have tried coming up with NFA1: third symbol is a, and NFA2: third from last symbol is a. Then NFA3 and NFA4 similar but with symbol of b. Then I use intersection of NFA1, NFA2, and intersection of NFA3, NFA4, and add $\epsilon$ transition. But things seem to go wrong here. When doing the intersection of, say, NFA1, and NFA2, obviously the new NFA would not accept strings such as aba, aaa.
I have been trying different methods but still stuck here for hours. Any help of hint would be much appreciated!
..a(.*a)?..|..b(.*b)?..|.aa.|.bb.|a.a|b.b
$\endgroup$