Complexity of checking if two words have an interleaving in a language
For a word $w=w_1\ldots w_{\ell}$ and for two integers $i,j$ with $1\le i\le j\le \ell$ we denote by $w(i,j)$ the subword $w_iw_{i+1}\ldots w_j$ of $w$.
Furthermore we let $w(0,0)$ denote the empty word.


Let $u=u_1\ldots u_m$ and $v=v_1\ldots v_n$ be the two words under consideration.
Assume that the context-free language $L$ is specified by a context-free grammar in Chomsky normal form.


Construct a dynamic program, where a state $[i,j,r,s,A]$ is specified by


two integers $i,j$ with $1\le i\le j\le m$ or $i=j=0$
two integers $r,s$ with $1\le r\le s\le n$ or $r=s=0$
a non-terminal symbol $A$ in the context-free grammar


For every state, decide whether in the context-free grammar there exists some derivation that starts with the non-terminal $A$ and that ends with some interleaving of the two words $u(i,j)$ and $w(r,s)$.
This decision can easily be made, if the states are handled in the right order (short subwords before longer subwords). 

All in all, this yields a polynomial time algorithm for the $L$-interleaving problem of any context-free language $L$.