Problem statement

https://binarysearch.com/problems/Longest-Consecutively-Increasing-Substring/

Solution

We need to traverse string and have:

  1. Q is the number of trailing question marks.

  2. L is the length of CISSa at the last seen non - ? character,

  3. c <= qmarks, in this case the CISSa starts in the trailing “?”s.
  4. L > 0 and L <= c <= L + Q. In this case the last non-? character can be in a CISSa, and the trailing ?s can be altered so that c continues the same CISSa.

Complexity

It is true O(n) (without 26) for time and space. Space can be made O(1).

Code

class Solution:
    def solve(self, s):
        s = [ord(x) - 97 for x in s]
        ans = L = Q = 0
        for c in s:
            if c == -34:
                Q += 1
            else:
                L = c + 1 if L <= c <= L + Q or c <= Q else 0
                Q = 0
            ans = max(ans, min(L + Q, 26))
        return ans