You are given a string s consisting of lowercase English letters.

In one operation, you can select any substring of s that is not the entire string and sort it in non-descending alphabetical order.

Return the minimum number of operations required to make s sorted in non-descending order. If it is not possible, return -1.

In other words, you want the final string to satisfy s[0] <= s[1] <= ... <= s[n-1]. Each operation lets you pick a contiguous portion of s — as long as it does not cover the whole string — and rearrange just that portion into sorted order. Your goal is to find the fewest such operations needed to fully sort s, or determine that no sequence of operations can achieve a sorted result.

The key restriction is that we can never sort the entire string in a single operation — we may only sort a proper substring. This constraint is what makes the problem interesting, because if we could sort the whole string, the answer would always be at most 1. Let's think about how many operations we really need under this rule.

First, if the string is already sorted, we don't need to do anything, so the answer is 0.

Now consider the smallest non-trivial case: a string of length 2 that is not sorted. The only substrings we can choose are the two single characters, but sorting a single character does nothing. We can never touch both characters together (that would be the whole string), so it is impossible to fix the order. This gives the answer -1.

For longer strings, the crucial observation is to focus on the minimum character mn and the maximum character mx. In a sorted string, every copy of mn must end up at the front and every copy of mx must end up at the back. The difficulty is that we cannot sort the full string at once, so the very first and very last positions are the troublesome spots.

• If s[0] is already mn, then the first character is already where it belongs. We can sort the substring s[1:] (which excludes only the first character, so it's a valid proper substring) and finish the job in 1 operation. The same logic applies if s[-1] is already mx: sort s[:-1] in 1 operation.

• If neither end is in the right place, but some mn or mx appears in the middle of the string, we can use that as a stepping stone. With one operation we move a mn to the front (or a mx to the back), and with a second operation we sort the rest. That gives 2 operations.

• Finally, if mn and mx only appear at the two ends (mn somewhere requiring it to reach the front, mx requiring the back) and nothing helpful sits in the middle, we still cannot do it in fewer than 3 moves: one operation to bring a needed character inward using a substring that includes both extremes, then operations to settle the front and back. This worst case yields the answer 3.

So the entire problem collapses into a small case analysis based on whether the string is sorted, whether its length is 2, and where mn and mx sit relative to the boundaries and the middle. By checking these conditions in order, we directly land on the answer of 0, 1, 2, 3, or -1.

We implement a direct case analysis that checks the conditions described above one by one, returning as soon as a case matches. No complex data structures are needed — just a few linear scans over the string.

Step 1: Check if already sorted.

We use pairwise(s) to iterate over every adjacent pair (a, b) and verify that a <= b holds for all of them. If the string is already in non-descending order, no work is needed:

if all(a <= b for a, b in pairwise(s)):
    return 0

Step 2: Handle the length-2 impossible case.

If the string is not sorted and has length 2, the only available substrings are single characters, which cannot change anything. Sorting is impossible, so we return -1:

if len(s) == 2:
    return -1

Step 3: Find the extreme characters.

We compute the minimum character mn and the maximum character mx of the string. These are the characters that must end up at the very front and very back of a sorted string, respectively:

mn, mx = min(s), max(s)

Step 4: Check the boundary positions (answer 1).

If s[0] already equals mn, the first position is correct, and sorting the proper substring s[1:] finishes the job. Symmetrically, if s[-1] equals mx, sorting s[:-1] works. Either way, one operation suffices:

if s[0] == mn or s[-1] == mx:
    return 1

Step 5: Check the middle for a helper character (answer 2).

If neither end is already correct, we look at the interior s[1:-1]. If any middle character equals mn or mx, we can use it as a stepping stone — one operation to position it and one more to sort the rest — giving a total of 2:

if any(c in [mn, mx] for c in s[1:-1]):
    return 2

Step 6: The worst case (answer 3).

If none of the above conditions hold — meaning mn and mx only sit at the two ends with no helper in the middle — we fall through to the final case requiring 3 operations:

return 3

Complexity Analysis:

• Time complexity: O(n), where n is the length of s. Each step (the sorted check, computing min/max, and scanning the middle) performs at most a single linear pass over the string.
• Space complexity: O(1), since we only store the two characters mn and mx and use constant extra space; the iterations with pairwise and any do not build additional structures proportional to the input.

This concise branching captures all five possible outcomes (0, 1, 2, 3, or -1) without any searching or simulation, relying entirely on the structural insight about where mn and mx must go.