[Spoiler alert]

Here is an overview of my O(n) solution: I created a 26x26 matrix that kept track of each possible 2-letter alternation. If at some point I got an invalid alternation for a pair (which happens when a letter follows itself in that alternation), that combination was discarded.

It's easier to explain with an example. Let's simplify the matrix to just 3 letters:

Input: acbab

Matrix begins empty:
  a b c
a 
b
c

We begin with the first 'a'. We update the 'a' row and column with that letter as last:
  a b c
a a a a
b a
c a

  a b c
a a a c
b a   c
c c c c

  a b c
a a b c
b b b b
c c b c

  a b c
a a a a
b a b b
c a b c

Finally, here comes the last letter: 'b'. Note that there is already a 'b' in combination c-b, so that alternation won't work:
  a b c
a a b a
b b b b 
c a b c

To get the longest alternation, I simply kept track of the amount of updates for each combination in another matrix. When a combination was detected as invalid, I marked its count with -1 and never updated it again.

I hope it's useful for you.