Given a string str consisting of only two characters 'a' and 'b'. You need to find the minimum steps required to make the string empty by removing consecutive a's and b's.
Example 1:
Input:
str = "bbaaabb"
Output:
2
Explanation:
Operation 1: Removal of all a's modifies str to "bbbb".
Operation 2: Removal of all remaining b's makes str
empty.
Therefore, the minimum number of operations required
is 2.
Example 2:
Input:
str = "aababaa"
Output:
3
Explanation:
Operation 1: Removal of b's modifies str to "aaabaa".
Operation 2: Removal of b's modifies str = "aaaaa".
Operation 3: Removal of all remaining a's makes str 
empty.
Therefore, the minimum number of operations required 
is 3.
Your Task:
You need to complete the function minSteps() which takes a string str as the only input parameter and returns an integer, denoting the minimum steps required to make the string empty.
Expected Time Complexity: O(N), where N = length of string str
Expected Space Complexity: O(1)
Constraints:
	1 <= str.length() <= 10^{5}
	'a' <= str[i] <= 'b'

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Greedy algorithms

Starter code: class Solution:

    def minSteps(self, str : str) -> int:

        # code here

        



Solutions:
class Solution:

	def minSteps(self, str: str) -> int:
		cnt = 1
		for i in range(len(str) - 1):
			if str[i] != str[i + 1]:
				cnt += 1
		return cnt // 2 + 1


class Solution:

	def minSteps(self, str: str) -> int:
		(a_count, b_count) = (0, 0)
		for (i, c) in enumerate(str):
			if i == 0 and c == 'a':
				a_count += 1
			if i == 0 and c == 'b':
				b_count += 1
			if c == 'a' and str[i - 1] != 'a':
				a_count += 1
			if c == 'b' and str[i - 1] != 'b':
				b_count += 1
		return min(a_count, b_count) + 1


class Solution:

	def minSteps(self, str: str) -> int:
		c = 0
		for i in range(len(str)):
			if str[i] != str[i - 1]:
				c += 1
		return c // 2 + 1


class Solution:

	def minSteps(self, str: str) -> int:
		count = 1
		n = len(str)
		for i in range(1, n):
			if str[i] != str[i - 1]:
				count += 1
		return count // 2 + 1


class Solution:

	def minSteps(self, s: str) -> int:
		if len(set(s)) == 1:
			return 1
		else:
			ca = 1
			cb = 1
			for i in range(0, len(s) - 1):
				if s[i] == 'a' and s[i + 1] == 'b':
					ca += 1
			for i in range(0, len(s) - 1):
				if s[i] == 'b' and s[i + 1] == 'a':
					cb += 1
			return max(ca, cb)


class Solution:

	def minSteps(self, str: str) -> int:
		asub = bsub = 0
		prev = ''
		for i in range(len(str)):
			if prev == str[i]:
				continue
			if str[i] == 'a':
				asub += 1
			else:
				bsub += 1
			prev = str[i]
		return min(asub, bsub) + 1


class Solution:

	def minSteps(self, str: str) -> int:
		s = ''
		c = 1
		if str[0] == 'a':
			s = 'b'
		else:
			s = 'a'
		n = len(str)
		for i in range(1, n):
			if str[i] == s and str[i - 1] != s:
				c += 1
		return c


class Solution:

	def minSteps(self, str: str) -> int:
		sec = ''
		count = 1
		if str[0] == 'a':
			sec = 'b'
		else:
			sec = 'a'
		for i in range(len(str)):
			if str[i] == sec and str[i - 1] != sec:
				count += 1
		return count


class Solution:

	def minSteps(self, str: str) -> int:
		a = 0
		b = 0
		if len(str) == 1:
			return 1
		if len(str) == 2:
			if str[0] != str[1]:
				return 2
			elif str[0] == 'a':
				return 1
			elif str[0] == 'b':
				return 1
		if str[0] != str[1]:
			a += 1
			b += 1
		elif str[0] == 'a':
			a += 1
		elif str[0] == 'b':
			b += 1
		for i in range(2, len(str)):
			if str[i] != str[i - 1] and str[i] == 'a':
				a += 1
			elif str[i] != str[i - 1] and str[i] == 'b':
				b += 1
		return min(a, b) + 1


class Solution:

	def minSteps(self, str: str) -> int:
		c = 0
		a = str[0]
		z = 'abcdefghijklmnopqrstuvwxyz'
		for i in str.split(a):
			if len(i) >= 1:
				if i[0] in z:
					c += 1
		return c + 1


class Solution:

	def minSteps(self, str: str) -> int:
		a = 0
		b = 0
		if str[0] == 'a':
			a += 1
			ele = 'a'
		else:
			b += 1
			ele = 'b'
		for i in str[1:]:
			if i == ele:
				continue
			else:
				if i == 'a':
					a += 1
				else:
					b += 1
				ele = i
		return min(a, b) + 1


class Solution:

	def minSteps(self, str: str) -> int:
		(ac, bc) = (0, 0)
		prev = '#'
		for i in str:
			if i == prev:
				continue
			elif i == 'a':
				ac += 1
			else:
				bc += 1
			prev = i
		return min(ac, bc) + 1


class Solution:

	def minSteps(self, str: str) -> int:
		res = 0
		ac = 0
		bc = 0
		prev = '-1'
		for i in range(len(str)):
			if prev == str[i]:
				continue
			if str[i] == 'a':
				ac += 1
			else:
				bc += 1
			prev = str[i]
		return min(ac, bc) + 1


class Solution:

	def minSteps(self, s: str) -> int:
		temp = ''
		for i in range(len(s)):
			if len(temp) == 0 or temp[len(temp) - 1] != s[i]:
				temp += s[i]
		return len(temp) // 2 + 1


class Solution:

	def minSteps(self, str: str) -> int:
		cnt = 1
		cur = str[0]
		for i in str[1:]:
			if i != cur:
				cnt += 1
				cur = i
		return cnt // 2 + 1


class Solution:

	def minSteps(self, str: str) -> int:
		(a_s, b_s) = [0, 0]
		i = 0
		while i < len(str):
			j = i + 1
			cnt = 1
			while j < len(str) and str[j] == str[i]:
				cnt += 1
				j += 1
			if str[i] == 'a':
				a_s += 1
			else:
				b_s += 1
			i = j
		return min(a_s, b_s) + 1


class Solution:

	def minSteps(self, str: str) -> int:
		count = 1
		m = str[0]
		prev = str[0]
		for item in str:
			if prev != item:
				if m != item:
					count += 1
				if prev == 'a':
					prev = 'b'
				else:
					prev = 'a'
		return count


class Solution:

	def minSteps(self, str: str) -> int:
		s1 = str
		tempa = 0
		tempb = 0
		prev = '#'
		for i in s1:
			if i == prev:
				continue
			if i == 'a':
				tempa += 1
			if i == 'b':
				tempb += 1
			prev = i
		return min(tempa, tempb) + 1


class Solution:

	def minSteps(self, str: str) -> int:
		d = {'a': 0, 'b': 0}
		curr = str[0]
		d[curr] = 1
		for i in str:
			if i != curr:
				curr = i
				d[curr] += 1
		return min(d['a'], d['b']) + 1


class Solution:

	def minSteps(self, str: str) -> int:
		n = len(str)
		a = 0
		b = 0
		prev = ''
		for i in str:
			if prev == i:
				continue
			if i == 'a':
				a += 1
			if i == 'b':
				b += 1
			prev = i
		return min(a, b) + 1


class Solution:

	def minSteps(self, strs: str) -> int:
		(a, b, n) = (0, 0, len(strs))
		(ap, bp) = (-1, -1)
		for i in range(n):
			if strs[i] == 'a':
				if ap == -1:
					ap = 1
					a += 1
				bp = -1
			if strs[i] == 'b':
				if bp == -1:
					bp = 1
					b += 1
				ap = -1
		return min(a, b) + 1


class Solution:

	def minSteps(self, str: str) -> int:
		str = list(str)
		sub = ''
		(acount, bcount) = (0, 0)
		for i in range(len(str)):
			if str[i] in sub or sub == '':
				sub += str[i]
			else:
				if 'a' in sub:
					acount += 1
				if 'b' in sub:
					bcount += 1
				sub = ''
				sub += str[i]
		return max(acount, bcount) + 1


class Solution:

	def minSteps(self, str: str) -> int:
		(a, b) = (0, 0)
		prev = None
		for s in str:
			if s == prev:
				continue
			if s == 'a':
				a += 1
			if s == 'b':
				b += 1
			prev = s
		return min(a, b) + 1


class Solution:

	def minSteps(self, str: str) -> int:
		acount = 0
		bcount = 0
		prev = '#'
		for i in range(len(str)):
			ch = str[i]
			if prev == ch:
				continue
			if ch == 'a':
				acount += 1
			else:
				bcount += 1
			prev = ch
		return min(acount, bcount) + 1


class Solution:

	def minSteps(self, ab: str) -> int:
		s = 'x'
		for x in ab:
			if s[-1] != x:
				s += x
		return 1 + min(s.count('a'), s.count('b'))


class Solution:

	def minSteps(self, str: str) -> int:
		st = str
		prev = '#'
		ac = 0
		bc = 0
		for i in st:
			if i == prev:
				continue
			if i == 'a':
				ac += 1
			if i == 'b':
				bc += 1
			prev = i
		return min(ac, bc) + 1


class Solution:

	def minSteps(self, str: str) -> int:
		ca = 0
		cb = 0
		for i in range(len(str)):
			if i < len(str) - 1 and str[i] == str[i + 1]:
				continue
			if str[i] == 'a':
				ca += 1
			else:
				cb += 1
		if ca == 0 and cb == 0:
			return 1
		return min(ca, cb) + 1


import math

class Solution:

	def minSteps(self, str: str) -> int:
		cnt = 1
		n = len(str)
		for i in range(n - 1):
			if str[i] != str[i - 1]:
				cnt += 1
		return math.floor(cnt / 2) + 1


class Solution:

	def minSteps(self, str: str) -> int:
		from math import ceil
		S = ''
		N = len(str)
		i = 0
		while i < N:
			S += str[i]
			j = i
			while i < N and str[i] == str[j]:
				i += 1
		a = ceil((len(S) + 1) / 2)
		return a


class Solution:

	def minSteps(self, str: str) -> int:
		n = len(str)
		c = 0
		i = 0
		j = n - 1
		val = str[0]
		while i <= j:
			if val == str[i]:
				i += 1
			elif val == str[j]:
				j -= 1
			else:
				c += 1
				val = str[i]
		return c + 1


class Solution:

	def minSteps(self, s):
		count = 1
		for i in range(1, len(s)):
			if s[i - 1] != s[i]:
				count += 1
		return count // 2 + 1


class Solution:

	def minSteps(self, str: str) -> int:
		consta = 0
		constb = 0
		prv = None
		for i in str:
			if prv != i:
				if i == 'a':
					consta += 1
				elif i == 'b':
					constb += 1
				prv = i
		return min(consta, constb) + 1


class Solution:

	def minSteps(self, str: str) -> int:
		c = 0
		old = 'b'
		for i in range(0, len(str)):
			if str[i] == 'a' and old != 'a':
				c += 1
				old = 'a'
				continue
			elif str[i] == 'b' and old == 'a':
				old = 'b'
		c1 = 0
		old = 'a'
		for i in range(0, len(str)):
			if str[i] == 'b' and old != 'b':
				c1 += 1
				old = 'b'
				continue
			elif str[i] == 'a' and old == 'b':
				old = 'a'
		return min(c, c1) + 1


class Solution:

	def minSteps(self, str1: str) -> int:
		(ac, bc, p) = (0, 0, '.')
		for i in range(len(str1)):
			k = str1[i]
			if p == k:
				continue
			if k == 'a':
				ac += 1
			else:
				bc += 1
			p = k
		return min(ac, bc) + 1


class Solution:

	def minSteps(self, str: str) -> int:
		violation = 0
		stack = []
		stack.append(str[0])
		for i in range(1, len(str)):
			if str[i] != stack[-1]:
				violation += 1
				stack.pop()
				stack.append(str[i])
		if violation % 2 != 0:
			return (violation + 1) // 2 + 1
		else:
			return violation // 2 + 1


class Solution:

	def minSteps(self, str: str) -> int:
		code = []
		a = 0
		b = 0
		flag = str[0]
		for i in str:
			if i == 'b':
				if i != flag:
					if flag == 'a':
						a += 1
					else:
						b += 1
					flag = i
			if i == 'a':
				if i != flag:
					if flag == 'a':
						a += 1
					else:
						b += 1
					flag = i
			flag = i
		if flag == 'a':
			a += 1
		else:
			b += 1
		if a > b:
			return b + 1
		else:
			return a + 1


import math

class Solution:

	def minSteps(self, s: str) -> int:
		n = len(s)
		c = 0
		n1 = 0
		n2 = 0
		n3 = 0
		i = 0
		while i < n:
			t = s[i]
			c += 1
			while i < n and t == s[i]:
				i += 1
		return int(math.ceil((c + 1) / 2))


class Solution:

	def minSteps(self, str: str) -> int:
		n = len(str)
		ans = 0
		for i in range(n - 1):
			if str[i] != str[i + 1]:
				ans += 1
		if ans & 1:
			ans = ans / 2 + 1
		else:
			ans /= 2
		return int(ans + 1)


class Solution:

	def minSteps(self, str: str) -> int:
		n = 1
		pos = str[0]
		for x in str:
			if pos == x:
				continue
			else:
				if pos == 'a':
					pos = 'b'
				elif pos == 'b':
					pos = 'a'
				n += 1
		return int(n / 2) + 1


class Solution:

	def minSteps(self, str: str) -> int:
		Acount = 0
		Bcount = 0
		pos = str[0]
		for x in str:
			if pos == x:
				continue
			elif pos == 'a':
				Acount += 1
				pos = 'b'
			elif pos == 'b':
				Bcount += 1
				pos = 'a'
		if pos == 'a':
			Acount += 1
		elif pos == 'b':
			Bcount += 1
		return min(Acount, Bcount) + 1


class Solution:

	def minSteps(self, str: str) -> int:
		acount = 0
		bcount = 0
		prev = ''
		for i in str:
			if i == 'a':
				if prev == 'a':
					pass
				else:
					acount += 1
			if i == 'b':
				if prev == 'b':
					pass
				else:
					bcount += 1
			prev = i
		return min(acount + 1, bcount + 1)


class Solution:

	def minSteps(self, str: str) -> int:
		char = 'x'
		d = dict()
		d[1] = 0
		d[-1] = 0
		val = 1
		for i in str:
			if not char == i:
				char = i
				val *= -1
				d[val] += 1
		m = min(d[1], d[-1])
		return m + 1


class Solution:

	def minSteps(self, str: str) -> int:
		dict = {'a': 0, 'b': 0}
		for i in range(len(str)):
			if i == len(str) - 1:
				if str[i] != str[i - 1]:
					dict[str[i]] += 1
					break
				else:
					dict[str[i - 1]] += 1
					break
			if str[i] != str[i + 1]:
				dict[str[i]] += 1
		if dict['a'] > dict['b']:
			return dict['b'] + 1
		else:
			return dict['a'] + 1


class Solution:

	def minSteps(self, str: str) -> int:
		str += 'p'
		ac = 0
		bc = 0
		for i in range(len(str) - 1):
			if str[i] != str[i + 1]:
				if str[i] == 'a':
					ac += 1
				else:
					bc += 1
		if bc > ac:
			return ac + 1
		else:
			return bc + 1


class Solution:

	def minSteps(self, str: str) -> int:
		block_counts = {'a': 0, 'b': 0}
		last = ' '
		for current in str:
			if current != last:
				block_counts[current] += 1
				last = current
		min_block_count = min(block_counts['a'], block_counts['b'])
		return min_block_count + 1


class Solution:

	def minSteps(self, str: str) -> int:
		x = str.count('ab')
		y = str.count('ba')
		return max(x, y) + 1


class Solution:

	def minSteps(self, str: str) -> int:
		str = list(str)
		x = str[0]
		t = 0
		m = 0
		for i in range(len(str)):
			if str[i] != x:
				m += 1
				if m == 1:
					t += 1
			if str[i] == x:
				m = 0
		return t + 1


class Solution:

	def minSteps(self, str: str) -> int:
		(counta, countb) = (0, 0)
		s = str
		for i in range(len(str)):
			if s[0] == 'a':
				counta += 1
				s = s.lstrip('a')
			else:
				countb += 1
				s = s.lstrip('b')
			if len(s) == 0:
				break
		if counta == countb:
			return countb + 1
		return max(counta, countb)


class Solution:

	def minSteps(self, str: str) -> int:
		(a, b) = (0, 0)
		(ch, p) = ('', '')
		for i in range(len(str)):
			ch = str[i]
			if p == ch:
				continue
			if ch == 'a':
				a = a + 1
			else:
				b += 1
			p = ch
		return min(a, b) + 1


class Solution:

	def minSteps(self, str: str) -> int:
		n = len(str)
		count = 1
		start = str[0]
		for i in range(1, n):
			if str[i] != start and str[i] != str[i - 1]:
				count = count + 1
		return count


class Solution:

	def minSteps(self, str: str) -> int:
		c = 0
		str = list(str)
		for i in range(1, len(str)):
			if str[i - 1] == str[i]:
				str[i - 1] = '_'
		a = str.count('a')
		b = str.count('b')
		if a > b:
			c = str.count('b')
		elif b > a:
			c = str.count('a')
		else:
			k = str.count('b')
			p = str.count('a')
			z = min(k, p)
			return z + 1
		return c + 1


class Solution:

	def minSteps(self, str: str) -> int:
		countA = 0
		countB = 0
		A = False
		if str[0] == 'a':
			A = True
			countA = 1
		else:
			countB = 1
		for i in str:
			if A:
				if i == 'b':
					A = False
					countB += 1
			elif i == 'a':
				A = True
				countA += 1
		return min(countA, countB) + 1