Orderly Class

This problem gives us a pair of strings and asks how many possible ways can we make a single substring reversal to get from the first to the second string.

Given the input length of 100k, the solution must be linear-ish.

Intuitively, we can say the following

1. If a prefix or postfix of the two strings matches, it doesn't have to be swapped
2. if a character doesn't match between the two strings, it MUST be swapped

So we can use this to find the smallest subset we must swap in order to make the strings match. This substring starts at the first non-matching character, and goes to the last non-matching character. We can prove that either this is a match or there is no match at all as follows

1. assume this string does not yield a match when flipped, but some larger substring does
2. we know that "right-pre" must match "left-post" and "left-pre" must match "right-post", so that they match after the flip
3. along with the above, the the segment contained between the left and right substrings must equal the post string after reversal
4. this contradicts our original assumption that the minimal-mismatched substring does not yield a match

So now that we have a minimal flip required, we know that any final solution must require us to expand one character to either side, and by step 2 in the proof above, those characters must be equal. This is seen clearly in the example in the problem, where the minimal mismatch is (xc), which when flipped creates a match. We see we get one more way to do it since the bounding character on either side is an 'a'.

This leads to the following linear algorithm

1. Iterate from the start to find the first mismatch
2. iterate from the back to find the last mismatch
3. check if flipping this minimal string causes a match
4. if so, check each pair of surrounding characters to see if we get a "bonus" match by including it