I was wondering if there is an algorithm for computing the Weyl group longest word starting with a particular choice.
For example, let $w_1$ and $w_2$ be defined as follows:
$$w_1= s_{i-1} s_{i-2} … s_1 s_{i-1} s_{i-2} … s_2 … s_{i-1} s_{i-2} s_{i-1};$$ $$w_2=s_{n} s_{n-1} … s_{j+1} s_{n} s_{n-1} … s_{j+2} … s_{n} s_{n-1} s_{n}.$$
How can we find the longest word $w_0$ of type $A$ starting with $w_1w_2$, assuming that $i<j$?
There is an inductive procedure: for the group $S_2$ the longest word is $s_1$. For $S_3$ it is $s_1 s_2 s_1$. For $S_4$ it is
$$s_1 s_2 s_3 s_1 s_2 s_1,$$ and for $S_5$ it is $$s_1 s_2 s_3 s_4 s_1 s_2 s_3 s_1 s_2 s_1.$$
The pattern should be clear. In general, if $w^{(n)}$ is the longest element of $S_n$, expressed as above as a reduced word, then $$w^{(n+1)}=s_1 s_2 \cdots s_{n} w^{(n)}$$ is also a reduced word.
To prove this, observe that $w^{(n)}$ is the permutation given by $$w^{(n)}(i)=n-i+1 \quad \hbox{for $1 \leq i \leq n$.}$$ Its length is $n(n-1)/2$, the cardinality of the set of positive roots. Now use $$(n+1)n/2=n+n(n-1)/2$$ and the fact that $$s_1 s_2 \cdots s_{n-1}=(123\cdots n)$$ is the $n$-cycle.
As a side note, it is a nice fact about these particular reduced words for $w_0$ that a reduced word for any element of $S_n$ can be obtained by deleting letters in a certain way.