Given a string s, determine if it is valid.
A string s is valid if, starting with an empty string t = "", you can transform t into s after performing the following operation any number of times:

Insert string "abc" into any position in t. More formally, t becomes tleft + "abc" + tright, where t == tleft + tright. Note that tleft and tright may be empty.

Return true if s is a valid string, otherwise, return false.
 
Example 1:
Input: s = "aabcbc"
Output: true
Explanation:
"" -> "abc" -> "aabcbc"
Thus, "aabcbc" is valid.
Example 2:
Input: s = "abcabcababcc"
Output: true
Explanation:
"" -> "abc" -> "abcabc" -> "abcabcabc" -> "abcabcababcc"
Thus, "abcabcababcc" is valid.

Example 3:
Input: s = "abccba"
Output: false
Explanation: It is impossible to get "abccba" using the operation.

Example 4:
Input: s = "cababc"
Output: false
Explanation: It is impossible to get "cababc" using the operation.

 
Constraints:

1 <= s.length <= 2 * 104
s consists of letters 'a', 'b', and 'c'

Difficulty: interview

Starter code:

class Solution:
    def isValid(self, s: str) -> bool:
        

Solutions:
class Solution:
    def isValid(self, s: str) -> bool:
        if not s:
            return True
        return self.isValid(s.replace('abc', '')) if s.replace('abc', '') != s else False


class Solution:
    def isValid(self, S: str) -> bool:
        stack = []
        for i in S:
            if i == 'c':
                if stack[-2:] !=['a','b']:
                    return False
                stack.pop()
                stack.pop()
            else:
                stack.append(i)
        return not stack
        
        
        
        


class Solution:
    def isValid(self, S: str) -> bool:
        l = ''
        for c in S:
            l += c
            if l[-3:]== 'abc':
                l = l[:-3]
        return not l

class Solution:
    def isValid(self, s: str) -> bool:
        stack = collections.deque()
        for char in s:
            if char == 'c' and len(stack) >= 2:
                if stack[-1] == 'b' and stack[-2] == 'a':
                    stack.pop()
                    stack.pop()
            else:
                stack.append(char)
        if len(stack) == 0:
            return True
        return False

class Solution:
    def isValid(self, s: str) -> bool:
        
        
        stack = []
        
        for c in s:
            if c == 'c':
                if ''.join(stack[-2:]) == 'ab':
                    stack.pop()
                    stack.pop()
                    continue
            stack.append(c)
        
        return not stack

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 3 != 0:
            return False
        if len(s) == 0:
            return True
        stack = []
        for i in s:
            if i != 'c':
                stack.append(i)
            elif len(stack) >= 2 and stack[-1] == 'b' and stack[-2] == 'a':
                stack.pop()
                stack.pop()
            else:
                stack.append(i)
        if len(stack) == 0:
            return True
        return False

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for ch in s:
            if ch == 'c':
                if len(stack) > 1 and stack[-1] == 'b' and stack[-2] == 'a':
                    stack.pop()
                    stack.pop()
            else:
                stack.append(ch)
        return not stack

class Solution:
    base = 'abc'
    base_len = 3
    
    def isValid(self, S: str) -> bool:
        stack = []
        for c in S:
            stack.append(c)
            if len(stack) >= 3:
                if stack[-1] == 'c' and stack[-2] == 'b' and stack[-3] == 'a':
                    stack.pop()
                    stack.pop()
                    stack.pop()
        return len(stack) == 0
            
#             if not stack:
#                 stack.append(c)
#             else:


from collections import deque
class Solution:
    def isValid(self, s: str) -> bool:
        stk = deque()
        for st in s:
            stk.append(st)
            if len(stk) >= 3:
                if stk[-1]=='c' and stk[-2]=='b' and stk[-3]=='a':
                        for i in range(3):
                            stk.pop()
        return len(stk)==0


# class Solution:
#     def isValid(self, s: str) -> bool:
#         element = 0
#         lg = len(s)
#         for j in range(lg):
#             element += 1
#             if element >= 3:
#                 if s[2]=='c' and s[1]=='b' and s[0]=='a':
#                     for i in range(2,-1,-1):
#                         del s[i]

#         return len(s)==0
            
from collections import deque
class Solution:
    def isValid(self, s: str) -> bool:
        stk = deque()
        for st in s:
            stk.append(st)
            if len(stk) >= 3:
                if stk[-1]=='c' and stk[-2]=='b' and stk[-3]=='a':
                        for i in range(3):
                            stk.pop()
        return len(stk)==0


class Solution:
    def isValid(self, s: str) -> bool:
        LAST_THREE = ['a','b','c']
        stack = [] 
        
        for index, _chr in enumerate(s):
            stack.append(_chr)
            if stack[-3:] == LAST_THREE:
                stack.pop()
                stack.pop()
                stack.pop()
                
        return len(stack) == 0

class Solution:
    def isValid(self, s: str) -> bool:
        rtn =''
        for i,char in enumerate(s):
            if char == 'a':
                rtn = rtn[:i] + 'abc' + rtn[i:]
        return rtn == s
                    
#             aabcbc,...abcabcababcc


class Solution:
    def isValid(self, s: str) -> bool:
        cnt = collections.Counter()
        stack = []
        for c in s:
            cnt[c] += 1
            if not cnt['a'] >= cnt['b'] >= cnt['c']:
                return False
            stack.append(c)
            while len(stack)>=3 and stack[-1]=='c' and stack[-2]=='b' and stack[-3]=='a':
                stack = stack[:-3]
            #print(stack)
        if stack:
            return False
        else:
            return True


class Solution:
    def isValid(self, s: str) -> bool:
        cnt = collections.Counter()
        stack = []
        for c in s:
            cnt[c] += 1
            if not cnt['a'] >= cnt['b'] >= cnt['c']:
                return False
            if c == 'c':
                if len(stack)>=2:
                    if stack[-1]=='b' and stack[-2]=='a':
                        stack.pop()
                        stack.pop()
                    else:
                        return False
            else:
                stack.append(c)
        return not stack


class Solution:
    def isValid(self, s: str) -> bool:
        while s:
            if 'abc' not in s:
                return False
            j = 0
            while j < len(s) - 2:
                if s[j:j+3] == 'abc':
                    s = s[:j] + s[j+3:]
                else:
                    j += 1
        return True

class Solution:
    def isValid(self, s: str) -> bool:
        
        
        dic = collections.defaultdict(list)
        
        for i, c in enumerate(s):
            dic[c].append(i)
        
        t = ''
        for i in dic['a']:
            t = t[:i] + 'abc' + t[i:]
        
        return t == s

class Solution:
    def isValid(self, s: str) -> bool:
        l = len(s)
        f = 0
        while s:
            i = 0
            f = 0
            while i<l:
                if s[i]=='a' and i+1<l and s[i+1]=='b' and i+2<l and s[i+2]=='c':
                    s = s[:i]+s[i+3:]
                    l-=3
                    f = 1
                else:
                    i+=1
            if f==0 and l!=0 and s!='':
                return False
        return True


class Solution:
    def isValid(self, s: str) -> bool:
        while s:
            tmp=s.replace('abc','')
            if tmp==s:break
            s=tmp
        return not s

class Solution:
    def isValid(self, s: str) -> bool:
        cnt = collections.Counter()
        stack = []
        for c in s:
            cnt[c] += 1
            if not cnt['a'] >= cnt['b'] >= cnt['c']:
                return False
            stack.append(c)
            while len(stack)>=3 and stack[-1]=='c' and stack[-2]=='b' and stack[-3]=='a':
                for _ in range(3):
                    stack.pop()
            #print(stack)
        if stack:
            return False
        else:
            return True


class Solution:
    def isValid(self, s: str) -> bool:
        findVal = s.find('abc')
        while findVal != -1:
            s = s[:findVal] + s[findVal+3:]
            findVal = s.find('abc')
        return s==''

class Solution:
    def isValid(self, s: str) -> bool:
        cnt = collections.Counter()
        stack = []
        for c in s:
            cnt[c] += 1
            if not cnt['a'] >= cnt['b'] >= cnt['c']:
                return False
            stack.append(c)
            while ''.join(stack[-3:]) == 'abc':
                stack = stack[:-3]
            #print(stack)
        if stack:
            return False
        else:
            return True


class Solution:
    def isValid0(self, S: str) -> bool:
        
        if len(S)<3:
            return False
        
        if len(S) == 3:
            if S == 'abc':
                return True
            else:
                return False
        
        # find 'abc'
        i=0
        while i<len(S) and S[i:i+3] != 'abc':
            i += 1
        
        if S[i:i+3] == 'abc':
            new_S = S[:i] + S[i+3:]
            return self.isValid(new_S)
        else:
            return False
        
    def isValid(self, S: str) -> bool:
        
        stack = []
        for c in S:
            if len(stack) < 2:
                stack.append(c)
            else:
                if stack[-2]+ stack[-1] + c =='abc':
                    stack.pop()
                    stack.pop()
                else:
                    stack.append(c)
        
        if len(stack) == 0:
            return True
        else:
            return False
        
        
        
        


class Solution:
    def isValid(self, s: str) -> bool:
        stack=[]
        i=0
        while(i<len(s) or (stack and len(stack)>2 and stack[-3:]==['a','b','c'])):
            while(stack and len(stack)>2 and stack[-3:]==['a','b','c']):
                
                stack.pop()
                stack.pop()
                stack.pop()
            if i<len(s):
                stack.append(s[i])
                i+=1
        #print('stack',stack)
        if not stack:
            return True
        return False

class Solution:
    def isValid(self, s: str) -> bool:
        while True:
            ns = s.replace('abc', '')
            if ns == '':
                return True
            if ns == s:
                return False
            s = ns

class Solution:
    def isValid(self, s: str) -> bool:
        indicesToDelete = set()
        for i in range(len(s)-2):
            substr = s[i:i+3]
            if substr =='abc':
                indicesToDelete.add(i)
                indicesToDelete.add(i+1)
                indicesToDelete.add(i+2)
        newS = ''
        for i in range(len(s)-1,-1,-1):
            if i not in indicesToDelete:
                newS += s[i]
        s = newS[::-1]
        left = 0
        right = len(s) -1

        while left < right:
            if s[left] =='a' and s[right] =='c':
                if s[left+1] =='b' and s[left+2] =='c':
                    left +=3
                elif s[right-1] =='b' and s[right-2] =='a':
                    right -=3
                elif s[left+1] == 'b':
                    left +=2
                    right -=1
                elif s[right-1] =='b':
                    left +=1
                    right -=2
                else:
                    return False
            else:
                return False
        return True


class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for i in range(len(s)):
            if stack == []:
                stack.append([])
                stack[-1].append(ord(s[i]))
            elif stack[-1][-1] + 1 == ord(s[i]):
                stack[-1].append(ord(s[i]))
            else:
                stack.append([ord(s[i])])
                
            if stack[-1] == [ord('a'), ord('b'), ord('c')]:
                stack.pop()
        return stack == []
            


class Solution:
    def isValid(self, S: str) -> bool:
        i = S.find('abc')
        while i != -1:
            S = S[:i] + S[i+3:]
            i = S.find('abc')
        return not S


class Solution:
    def isValid(self, s: str) -> bool:
        while len(s) > 3:
            i = s.find('abc')
            if i == -1:
                return False
            s = s[:i] + s[i + 3:]
        return not s or s == 'abc'

class Solution:
    def isValid(self, S: str) -> bool:
        stack = []
        for c in S:
            stack.append(c)
            if ''.join(stack[-3:]) == 'abc':
                stack = stack[:-3]
        return len(stack) == 0

class Solution:
    def isValid(self, S: str) -> bool:
        stack = []
        for c in S:
            stack.append(c)
            while stack and stack[-1] == 'c' and len(stack) >= 3 and stack[-2] == 'b' and stack[-3] == 'a':
                stack = stack[:-3]
        
        return not stack

class Solution:
    def isValid(self, s: str) -> bool:
        while s.find('abc') > -1:
            i = s.find('abc')
            s = s[:i] + s[i+3:]
        return s == ''
        


class Solution:
    def isValid(self, s: str) -> bool:
        while s.find('abc') >= 0:
            s = s.replace('abc', '')
        return s == ''

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for c in s:
            stack.append(c)
            while ''.join(stack[-3:]) == 'abc':
                stack = stack[:-3]
            #print(stack)
        if stack:
            return False
        else:
            return True


class Solution:
    def isValid(self, s: str) -> bool:
        s = list(s)
        left = 0
        while len(s) > 2 and left < len(s)-2:
            if s[left:left+3] == ['a', 'b', 'c']:
                s.pop(left+2)
                s.pop(left+1)
                s.pop(left)
                left -= 2
            else:
                left += 1
        if s:
            return False
        else:
            return True


class Solution:
    def isValid(self, S: str) -> bool:
        st = []
        for i, s in enumerate(S):
            st.append(s)
            while st[-3:] == ['a','b','c']:
                st = st[:-3]
        return len(st) == 0

class Solution:
    def isValid(self, S: str) -> bool:
        stack = []
        for i in S:
            if i == 'c':
                if stack[-2:] != ['a', 'b']:
                    return False
                stack.pop()
                stack.pop()
            else:
                stack.append(i)
        return not stack


'''
abc abc
a abc bc
ab abc c

Keep a stack that remembers the current letter for each depth level

for example:
aabcbc
  123
1 [a, b]
2 [a]
3 [b]

'''


class Solution:
    def isValid(self, s: str) -> bool:
        stack = list()
        
        for ch in s:
            if ch == 'a':
                stack.append('a')
            elif ch == 'b':
                if stack and stack[-1] == 'a':
                    stack[-1] = 'b'
                else:
                    return False
            elif ch == 'c':
                if stack and stack[-1] == 'b':
                    stack.pop()
                else:
                    return False
            else:
                return False
        
        return (len(stack) == 0)

class Solution:
    def isValid(self, s: str) -> bool:
        d=[]
        for i in s:
            if i=='c':
                if d[-2:]!=['a','b']:return False
                d.pop();d.pop()
            else:d.append(i)
        return not d