On the other hand, it&#x27;s just a matter of maintaining the number of open parentheses. Similar fact, one can&#x27;t count string lengths in linear time (because lengths can be arbitrarily large). But for concerns of implementation it&#x27;s just O(n).