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'

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Data structures

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


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


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]
		if stack:
			return False
		else:
			return True


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:
		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]
		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
		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)
			elif 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
		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') >= 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]
		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 = 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