Pushdown Automata for words x#y where x and y are different words over {0,1} that share one similarity
Here is the critical observation.  We can combine the two conditions, there must be at least one difference and there must be at least one similarity between $x$ and $y$ into the following one condition.



Let $x=x_1x_2\cdots x_m$ and $y=y_1y_2\cdots y_n$, where $x_1, x_2,\cdots, x_m,y_1, y_2,\cdots, y_n\in \Sigma$. Then $x\#y$ is a word in the language if and only if there exists an index $i$ such that 


$x_i\not=y_i$ and $x_{i+1} =y_{i+1}$ or,
$x_i=y_i$ and we do not have $x_{i+1} =y_{i+1}$.


The precise meaning of "we do not have $x_{i+1} =y_{i+1}$" is either exactly one of $x_{i+1}$ and $y_{i+1}$ is defined or $x_{i+1}\not= y_{i+1}$.



The basic motivation of the idea above is that an PDA can only keep track of one unbounded counter. So we should compress two unbounded counters, the index of the similarity and the index of the difference into one unbounded counter.