Determine if a string is Sturmian

A finite binary string is "Sturmian" if for every two contiguous substrings $x$ and $y$ of the same length, the number of $0$s in $x$ and $y$ differs by at most 1.

Your program should take a finite binary string and output one of two distinct values. The first if the input is Sturmian the other if the input is not Sturmian.

This is code-golf so the goal is to minimize the size of your source code as measured in bytes.

Bonus

This problem is solvable in worst-case linear time complexity. I encourage people to submit linear time solutions. Although it is not necessary, I give my official blessing for linear time solutions to be scored separately from slower solutions. Just as different programming languages are not competing against each other

In fact I consider this in some sense the real challenge. There seems to me more dimension for golfing strategy in the linear time case.

In order for this to work on the leader board I suggest that submissions append "linear" to the language name. e.g. Elm linear, 240 bytes

Test cases

Please do not try to guess the property based on the test-cases. Please read the description, and if something is unclear ask about it.

I have included the falsifying substrings in the Non-Sturmian cases. Your solution is not required to, or even permitted to, output these extra strings.

0110 -> Sturmian
0011 -> Non-Sturmian (00, 11)
100001000100001 -> Sturmian
1000001000010001 -> Non-Sturmian (00000, 10001)
10010100100101001001010010 -> Sturmian
10010100100100101001010010 -> Non-Sturmian (00100100, 10100101)