Problem statement

https://binarysearch.com/problems/Monotonous-String-Groups/

Solution

The idea is to use groupby first to remove adjacent equal elements. Then we use greedy strategy, where we create groups of monotonic elements.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, s):
        s = "".join(c for c, _ in groupby(s))
        n = len(s)

        ans = i = 0
        while i < n:
            ans += 1
            if i + 1 == n: break
            elif s[i + 1] > s[i]:
                while i + 1 < n and s[i + 1] > s[i]: i += 1
            else:
                while i + 1 < n and s[i + 1] < s[i]: i += 1
            i += 1

        return ans