from collections import Counter
class Solution(object):
    def dfs(self, s, pos, stack):
        if stack + self.min_possible_opening[-1] - self.min_possible_opening[pos] > self.max_possible_closing[-1] - self.max_possible_closing[pos]:
            return False
        if stack + self.max_possible_opening[-1] - self.max_possible_opening[pos] < self.min_possible_closing[-1] - self.min_possible_closing[pos]:
            return False
        if pos == len(s):
            return not stack
        if s[pos] == '(':
            stack += 1
            if self.dfs(s, pos + 1, stack):
                return True
            stack -= 1
        elif s[pos] == ')':
            if not stack:
                return False
            else:
                stack -= 1
                if self.dfs(s, pos + 1, stack):
                    return True
                stack += 1
        else:
            if stack: # treat as ')'
                stack -= 1
                if self.dfs(s, pos + 1, stack):
                    return True
                stack += 1
            # treat as '('
            stack += 1
            if self.dfs(s, pos + 1, stack):
                return True
            stack -= 1

            # treat as ''
            if self.dfs(s, pos + 1, stack):
                return True
        return False

    def checkValidString(self, s):
        """
        :type s: str
        :rtype: bool
        """
        c = Counter(s)
        mpo, mpc = c['('] + c['*'], c[')'] + c['*']

        self.max_possible_opening = [0]
        self.min_possible_opening = [0]
        self.max_possible_closing = [0]
        self.min_possible_closing = [0]
        for c in s:
            self.min_possible_opening.append(self.min_possible_opening[-1] + (c == '('))
            self.max_possible_opening.append(self.max_possible_opening[-1] + (c != ')'))
            self.min_possible_closing.append(self.min_possible_closing[-1] + (c == ')'))
            self.max_possible_closing.append(self.max_possible_closing[-1] + (c != '('))

        return self.dfs(s, 0, 0)

class Solution(object):

    def checkValidString(self, s):
        """
        :type s: str
        :rtype: bool
        """
        lowest, highest = 0, 0
        for c in s:
            if c == '(':
                lowest += 1
                highest += 1
            elif c == ')':
                if lowest > 0:
                    lowest -= 1
                highest -= 1
                if highest < 0:
                    return False
            else:
                if lowest > 0:
                    lowest -= 1
                highest += 1
        return lowest == 0

Add py solution for 678. Valid Parenthesis String
Add py solution for 678. Valid Parenthesis String

678. Valid Parenthesis String: https://leetcode.com/problems/valid-parenthesis-string/

Approach2:
    Maintain the lowest/highest possible stack size and check if one of
    them is invalid
    O(n) time, O(1) size

- from collections import Counter
  class Solution(object):
-     def dfs(self, s, pos, stack):
-         if stack + self.min_possible_opening[-1] - self.min_possible_opening[pos] > self.max_possible_closing[-1] - self.max_possible_closing[pos]:
-             return False
-         if stack + self.max_possible_opening[-1] - self.max_possible_opening[pos] < self.min_possible_closing[-1] - self.min_possible_closing[pos]:
-             return False
-         if pos == len(s):
-             return not stack
-         if s[pos] == '(':
-             stack += 1
-             if self.dfs(s, pos + 1, stack):
-                 return True
-             stack -= 1
-         elif s[pos] == ')':
-             if not stack:
-                 return False
-             else:
-                 stack -= 1
-                 if self.dfs(s, pos + 1, stack):
-                     return True
-                 stack += 1
-         else:
-             if stack: # treat as ')'
-                 stack -= 1
-                 if self.dfs(s, pos + 1, stack):
-                     return True
-                 stack += 1
-             # treat as '('
-             stack += 1
-             if self.dfs(s, pos + 1, stack):
-                 return True
-             stack -= 1
- 
-             # treat as ''
-             if self.dfs(s, pos + 1, stack):
-                 return True
-         return False
  
      def checkValidString(self, s):
          """
          :type s: str
          :rtype: bool
          """
-         c = Counter(s)
-         mpo, mpc = c['('] + c['*'], c[')'] + c['*']
+         lowest, highest = 0, 0
+         for c in s:
+             if c == '(':
+                 lowest += 1
+                 highest += 1
+             elif c == ')':
+                 if lowest > 0:
+                     lowest -= 1
+                 highest -= 1
+                 if highest < 0:
+                     return False
+             else:
+                 if lowest > 0:
+                     lowest -= 1
+                 highest += 1
+         return lowest == 0
  
-         self.max_possible_opening = [0]
-         self.min_possible_opening = [0]
-         self.max_possible_closing = [0]
-         self.min_possible_closing = [0]
-         for c in s:
-             self.min_possible_opening.append(self.min_possible_opening[-1] + (c == '('))
-             self.max_possible_opening.append(self.max_possible_opening[-1] + (c != ')'))
-             self.min_possible_closing.append(self.min_possible_closing[-1] + (c == ')'))
-             self.max_possible_closing.append(self.max_possible_closing[-1] + (c != '('))
- 
-         return self.dfs(s, 0, 0)
- 
Add py solution for 678. Valid Parenthesis String
## Code Before:
from collections import Counter
class Solution(object):
    def dfs(self, s, pos, stack):
        if stack + self.min_possible_opening[-1] - self.min_possible_opening[pos] > self.max_possible_closing[-1] - self.max_possible_closing[pos]:
            return False
        if stack + self.max_possible_opening[-1] - self.max_possible_opening[pos] < self.min_possible_closing[-1] - self.min_possible_closing[pos]:
            return False
        if pos == len(s):
            return not stack
        if s[pos] == '(':
            stack += 1
            if self.dfs(s, pos + 1, stack):
                return True
            stack -= 1
        elif s[pos] == ')':
            if not stack:
                return False
            else:
                stack -= 1
                if self.dfs(s, pos + 1, stack):
                    return True
                stack += 1
        else:
            if stack: # treat as ')'
                stack -= 1
                if self.dfs(s, pos + 1, stack):
                    return True
                stack += 1
            # treat as '('
            stack += 1
            if self.dfs(s, pos + 1, stack):
                return True
            stack -= 1

            # treat as ''
            if self.dfs(s, pos + 1, stack):
                return True
        return False

    def checkValidString(self, s):
        """
        :type s: str
        :rtype: bool
        """
        c = Counter(s)
        mpo, mpc = c['('] + c['*'], c[')'] + c['*']

        self.max_possible_opening = [0]
        self.min_possible_opening = [0]
        self.max_possible_closing = [0]
        self.min_possible_closing = [0]
        for c in s:
            self.min_possible_opening.append(self.min_possible_opening[-1] + (c == '('))
            self.max_possible_opening.append(self.max_possible_opening[-1] + (c != ')'))
            self.min_possible_closing.append(self.min_possible_closing[-1] + (c == ')'))
            self.max_possible_closing.append(self.max_possible_closing[-1] + (c != '('))

        return self.dfs(s, 0, 0)

## Instruction:
Add py solution for 678. Valid Parenthesis String
## Code After:
class Solution(object):

    def checkValidString(self, s):
        """
        :type s: str
        :rtype: bool
        """
        lowest, highest = 0, 0
        for c in s:
            if c == '(':
                lowest += 1
                highest += 1
            elif c == ')':
                if lowest > 0:
                    lowest -= 1
                highest -= 1
                if highest < 0:
                    return False
            else:
                if lowest > 0:
                    lowest -= 1
                highest += 1
        return lowest == 0
