I like the use of the direction enum
How is this O(n/2) if you're still doing ~n comparisons? The loop runs n/2 times but you do 2 comparisons per loop. O(n) is still great though, better than sorting
Avoids memory usage and uses a cool property of the golden ratio. Love it.
More generally, solution is O(n*R) where n is the length of the sentence and R is the size of your alphabet (disregarding the call of toLowerCase() in every iteration of the loop) – but it can still be done in O(n).