You are viewing a single comment's thread. Return to all comments →
There is even simpler logic, along the same lines, though it takes one more mental step to prove it. There's no need to test whether the string length is odd or even. The correctness test is a little different than yours, of course.
here's the proof:
even + even = even
odd + odd = even
odd + even = odd
if the string length is even then it must have an even number of odd substrings, meaning 0, 2, 4...
Otherwise the length would be odd.
this means that a correct test for the odd length should also catch valid even length strings.