There is a string of size n containing only 'A' and 'O'. 'A' stands for Apple, and 'O' stands for Orange. We have m number of spells, each spell allows us to convert an orange into an apple. 
Find the longest subarray of apples you can make, given a string and the value of m.
Example 1:
Input:
N = 5
M = 1
arr[] = 'AAOAO'
Output: 4 
Explanation: Changing the orange at 
3rd position into an apple gives 
us the maximum possible answer.
Example 2:
Input:
N = 5
M = 1
arr = 'AOOAO'
Output: 2
Explanation: Changing any orange into 
an apple will give us a sequence 
of length 2.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function appleSequence() which takes the array in the form of a string, its size n, and an integer m as input parameters and returns the largest apple sequences after converting m oranges.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)
Constraints:
1 <= m <= n <= 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Amortized analysis

Implementation

Starter code: #User function Template for python3



class Solution:

    def appleSequences(self, n, m, arr):

        # code here 

        

        

Solutions:
class Solution:

	def appleSequences(self, n, m, arr):
		i = 0
		j = 0
		answer = 0
		while j < n:
			if arr[j] == 'A':
				j += 1
			elif m > 0:
				m -= 1
				j += 1
			else:
				while m == 0:
					if arr[i] == 'O':
						m += 1
					i += 1
			answer = max(answer, j - i)
		return answer


class Solution:

	def appleSequences(self, n, m, arr):
		(left, right) = (0, 0)
		(max_len, orange) = (0, 0)
		while right < len(arr):
			if arr[right] == 'O':
				orange += 1
			while orange > m:
				if arr[left] == 'O':
					orange -= 1
				left += 1
			max_len = max(max_len, right - left + 1)
			right += 1
		return max_len


class Solution:

	def appleSequences(self, n, m, arr):
		(i, j) = (0, 0)
		counta = 0
		counto = 0
		ans = 0
		while j < n:
			if arr[j] == 'A':
				counta += 1
			elif counto < m:
				counto += 1
			else:
				while i < j and arr[i] != 'O':
					i += 1
					counta -= 1
				i += 1
			ans = max(ans, counta + counto)
			j += 1
		return ans


class Solution:

	def appleSequences(self, n, m, arr):
		start = end = ans = 0
		while end < len(arr):
			if arr[end] == 'O':
				m += -1
			while m < 0 and start < len(arr):
				if arr[start] == 'O':
					m += 1
				start += 1
			ans = max(ans, end - start + 1)
			end += 1
		return ans


class Solution:

	def appleSequences(self, n, m, arr):
		(right, left) = (0, 0)
		ans = 0
		while right < n:
			if arr[right] == 'A':
				right += 1
			elif m > 0:
				right += 1
				m -= 1
			else:
				ans = max(ans, right - left)
				while arr[left] != 'O':
					left += 1
				left += 1
				m += 1
		ans = max(ans, right - left)
		return ans


class Solution:

	def appleSequences(self, n, m, arr):
		(fp, sp, ex) = (0, 0, 0)
		ans = 0
		while sp < n:
			if arr[sp] == 'A':
				sp += 1
			elif ex == m:
				while arr[fp] != 'O':
					fp += 1
				fp += 1
				sp += 1
			else:
				ex += 1
				sp += 1
			ans = max(ans, sp - fp)
		return ans


class Solution:

	def appleSequences(self, n, m, arr):
		i = 0
		j = 0
		c = 0
		while j < n:
			if arr[j] == 'O':
				m -= 1
				while m < 0:
					if arr[i] == 'O':
						m += 1
					i += 1
			c = max(c, j - i + 1)
			j += 1
		return c


class Solution:

	def appleSequences(self, n, m, arr):
		l = 0
		r = 0
		maxi = 0
		count = 0
		while r < n:
			if arr[r] == 'O':
				count += 1
			while count > m:
				if arr[l] == 'O':
					count -= 1
				l += 1
			maxi = max(maxi, r - l + 1)
			r += 1
		return maxi


class Solution:

	def appleSequences(self, n, m, arr):
		maxi = 0
		end = 0
		start = 0
		count = 0
		while end < n:
			if arr[end] == 'O':
				count += 1
			while start < n and count > m:
				if arr[start] == 'O':
					count -= 1
				start += 1
			maxi = max(maxi, end - start + 1)
			end += 1
		return maxi


class Solution:

	def appleSequences(self, n, m, arr):
		i = 0
		j = 0
		m1 = 0
		d = {}
		while j < len(arr):
			if arr[j] in d:
				d[arr[j]] += 1
			else:
				d[arr[j]] = 1
			if arr[j] == 'O':
				m -= 1
			if m >= 0:
				m1 = max(m1, j - i + 1)
				j += 1
			if m < 0:
				while m < 0:
					d[arr[i]] -= 1
					if arr[i] == 'O':
						m += 1
					if d[arr[i]] == 0:
						del d[arr[i]]
					i += 1
				j += 1
		return m1


class Solution:

	def appleSequences(self, n, m, arr):
		(left, right) = (0, 0)
		o_count = 0
		ans = 0
		first_o = None
		while right < n:
			if arr[right] == 'O':
				o_count += 1
				if o_count > m:
					ans = max(ans, right - left)
					while left < n and o_count > m:
						if arr[left] == 'O':
							o_count -= 1
						left += 1
				right += 1
			else:
				right += 1
		return max(ans, right - left)


class Solution:

	def appleSequences(self, n, k, a):
		c = j = len = 0
		for i in range(0, n):
			if a[i] == 'O':
				c += 1
			while c > k:
				if a[j] == 'O':
					c -= 1
				j += 1
			len = max(len, i - j + 1)
		return len


class Solution:

	def appleSequences(self, n, m, arr):
		start = 0
		end = 0
		curr = 0
		maxx = 0
		while end < n:
			if arr[end] == 'A':
				maxx = max(maxx, end - start + 1)
			if arr[end] == 'O':
				curr += 1
				if curr > m:
					while start < end and arr[start] != 'O':
						start += 1
					start += 1
				maxx = max(maxx, end - start + 1)
			end += 1
		return maxx


class Solution:

	def appleSequences(self, n, m, arr):
		(left, ans) = (0, 0)
		for right in range(n):
			if arr[right] == 'O':
				m -= 1
			while left <= right and m < 0:
				if arr[left] == 'O':
					m += 1
				left += 1
			ans = max(ans, right - left + 1)
		return ans


class Solution:

	def appleSequences(self, n, m, arr):
		ans = 0
		i = 0
		count = 0
		for j in range(n):
			if arr[j] == 'O':
				count += 1
			while i < j and count > m:
				if arr[i] == 'O':
					count -= 1
				i += 1
			ans = max(ans, j - i + 1)
		return ans


class Solution:

	def appleSequences(self, n, m, arr):
		ma = 0
		low = 0
		for i in range(n):
			if arr[i] == 'A':
				ma = max(ma, i - low + 1)
			else:
				if m > 0:
					m -= 1
				else:
					while arr[low] == 'A':
						low += 1
					low += 1
				ma = max(ma, i - low + 1)
		return ma


class Solution:

	def appleSequences(self, n, m, arr):
		cntMap = {'A': 0, 'O': 0}
		l = 0
		res = 1
		for r in range(len(arr)):
			cntMap[arr[r]] += 1
			while r - l + 1 - cntMap['A'] > M:
				cntMap[arr[l]] -= 1
				l += 1
			res = max(res, r - l + 1)
		return res


class Solution:

	def appleSequences(self, n, m, a):
		i = 0
		j = 0
		pr = 0
		maxi = 0
		while j < n:
			if a[j] == 'A':
				maxi = max(maxi, j - i + 1)
			if a[j] == 'O':
				pr += 1
				if pr > m:
					while i < j and a[i] != 'O':
						i += 1
					i += 1
					pr -= 1
				maxi = max(maxi, j - i + 1)
			j += 1
		return maxi


class Solution:

	def appleSequences(self, n, m, arr):
		ans = int()
		start = int()
		ind = int()
		cnt = 0
		flips = 0
		while ind < n:
			if arr[ind] == 'A':
				cnt += 1
			else:
				flips += 1
				cnt += 1
			while flips > m:
				flips -= 1 if arr[start] == 'O' else 0
				start += 1
			ans = max(ans, ind - start + 1)
			ind += 1
		return ans


class Solution:

	def appleSequences(self, n, m, arr):
		(ml, en, st, ct) = (0, 0, 0, 0)
		while en < n:
			if arr[en] == 'O':
				ct += 1
			while st < n and ct > m:
				if arr[st] == 'O':
					ct -= 1
				st += 1
			ml = max(ml, en - st + 1)
			en += 1
		return ml


class Solution:

	def appleSequences(self, n, m, A):
		D = []
		M = 0
		c = 0
		i = 0
		j = 0
		for i in range(n):
			if A[i] == 'A':
				c += 1
			elif m > 0:
				D.append(i)
				c += 1
				m -= 1
			else:
				x = D[j]
				j += 1
				D.append(i)
				c = i - x
			if c > M:
				M = c
		return M


class Solution:

	def appleSequences(self, n, m, s):
		(st, en, oc, ml) = (0, 0, 0, 0)
		while en < n:
			if s[en] == 'O':
				oc += 1
			while oc > m:
				if s[st] == 'O':
					oc -= 1
				st += 1
			ml = max(ml, en - st + 1)
			en += 1
		return ml


class Solution:

	def appleSequences(self, n, m, arr):
		st = 0
		end = 0
		ans = 0
		while end != n:
			if m > 0:
				if arr[end] == 'O':
					m -= 1
			elif arr[end] == 'O':
				while arr[st] != 'O':
					st += 1
				st += 1
			ans = max(ans, end - st + 1)
			end += 1
		return ans


class Solution:

	def appleSequences(self, n, m, arr):
		lon = 0
		tt = 0
		mx = 0
		nt = 0
		for lon in range(n):
			if arr[lon] == 'O':
				nt += 1
			while tt < n and nt > m:
				if arr[tt] == 'O':
					nt -= 1
				tt += 1
			mx = max(mx, lon - tt + 1)
		return mx


class Solution:

	def appleSequences(self, n, m, arr):
		d = {'O': 0}
		res = 0
		l = 0
		for r in range(n):
			d[arr[r]] = d.get(arr[r], 0) + 1
			while d['O'] > m:
				d[arr[l]] -= 1
				l += 1
			res = max(res, r - l + 1)
		return res


class Solution:

	def appleSequences(self, n, m, arr):
		l = 0
		r = 0
		max_ = -999999999
		c = 0
		l = 0
		for r in range(n):
			if arr[r] == 'O':
				c += 1
			if c <= m:
				max_ = max(max_, r - l + 1)
			while c > m:
				if arr[l] == 'O':
					c -= 1
				l += 1
		return max_


class Solution:

	def appleSequences(self, n, m, arr):
		(left, right) = (0, 0)
		res = 0
		curo = 0
		while right < len(arr):
			if arr[right] == 'A':
				pass
			else:
				curo += 1
				if curo > m:
					while left < right and arr[left] == 'A':
						left += 1
					left += 1
			res = max(res, right - left + 1)
			right += 1
		return res


class Solution:

	def appleSequences(self, n, m, arr):
		(maxi, c, j) = (0, 0, 0)
		for i in range(n):
			if arr[i] == 'O':
				c += 1
			while c > m:
				if arr[j] == 'O':
					c -= 1
				j += 1
			maxi = max(i - j + 1, maxi)
		return maxi


class Solution:

	def appleSequences(self, n, m, arr):
		maxSequence = 0
		start = 0
		end = 0
		spells_used = 0
		while end < n:
			if arr[end] == 'O':
				spells_used += 1
			while start < n and spells_used > m:
				if arr[start] == 'O':
					spells_used -= 1
				start += 1
			maxSequence = max(maxSequence, end - start + 1)
			end += 1
		return maxSequence


class Solution:

	def appleSequences(self, n, m, arr):
		start = 0
		patch = 0
		lis = []
		lead = 0
		match = []
		count = 0
		for i in range(n):
			if arr[i] == 'A' and i < n - 1:
				continue
			elif arr[i] == 'O':
				match.append(i)
				if patch == m:
					lis.append(i - start)
					start = match[lead]
					lead += 1
					start += 1
				else:
					patch += 1
		lis.append(n - start)
		return max(lis)


class Solution:

	def appleSequences(self, n, m, arr):
		q = []
		j = 0
		idx = 0
		ans = 0
		curr = 0
		while j < n:
			if m > 0:
				if arr[j] == 'O':
					m -= 1
			elif arr[j] == 'O':
				while arr[idx] != 'O':
					idx += 1
				idx += 1
			val = j - idx + 1
			ans = ans if ans > val else val
			j += 1
		return ans


class Solution:

	def appleSequences(self, n, m, arr):
		start = 0
		end = 0
		cnto = 0
		maxlen = 0
		for end in range(n):
			if arr[end] == 'O':
				cnto += 1
			while cnto > m:
				if arr[start] == 'O':
					cnto -= 1
				start += 1
			maxlen = max(maxlen, end - start + 1)
		return maxlen


class Solution:

	def appleSequences(self, n, m, arr):
		res = 0
		count = {'A': 0, 'O': 0}
		l = 0
		maxf = 0
		for r in range(n):
			count[arr[r]] = 1 + count.get(arr[r], 0)
			maxf = count['A']
			while r - l + 1 - maxf > m:
				count[arr[l]] -= 1
				l += 1
			res = max(res, r - l + 1)
		return res
		return res


class Solution:

	def appleSequences(self, n, m, arr):
		l = 0
		r = 0
		used = m
		maxSize = 0
		currSize = 0
		while l <= r and r < n:
			curr = arr[r]
			if curr == 'A':
				currSize += 1
			else:
				if used > 0:
					currSize += 1
				else:
					while l < r and used < 1:
						currSize -= 1
						if arr[l] == 'O':
							used += 1
						l += 1
					currSize += 1
				used -= 1
			r += 1
			maxSize = max(maxSize, currSize)
		return max(maxSize, currSize)


class Solution:

	def appleSequences(self, n, m, arr):
		start = 0
		end = 0
		res = 0
		while start < n and end < n:
			if m > 0:
				if arr[end] == 'O':
					m -= 1
			elif arr[end] == 'O':
				while start < n and arr[start] != 'O':
					start += 1
				start += 1
			res = max(res, end - start + 1)
			end += 1
		return res


class Solution:

	def appleSequences(self, n, m, arr):
		ans = 0
		(i, j, count) = (0, 0, 0)
		while j < n:
			if arr[j] == 'A':
				ans = max(ans, j - i + 1)
			elif arr[j] == 'O':
				count += 1
				while i <= j and count > m:
					if arr[i] == 'O':
						count -= 1
					i += 1
				ans = max(ans, j - i + 1)
			j += 1
		return ans


class Solution:

	def appleSequences(self, n, m, arr):
		N = n
		M = m
		ma = 0
		c = 0
		spells_left = M
		for i in range(N):
			if arr[i] == 'A':
				c += 1
			elif spells_left > 0:
				c += 1
				spells_left -= 1
			else:
				ma = max(ma, c)
				start = i - c
				for j in range(start, i):
					if arr[j] == 'O':
						break
				c -= j - start
		return max(ma, c)


class Solution:

	def appleSequences(self, n, m, a):
		ans = 0
		start = 0
		for i in range(n):
			if a[i] == 'O':
				while start < i and m <= 0:
					if a[start] == 'O':
						m += 1
					start += 1
				m -= 1
			ans = max(ans, i - start + 1)
		return ans


class Solution:

	def appleSequences(self, n, m, arr):
		ans = float('-inf')
		count = 0
		i = 0
		j = 0
		k = 0
		while i < n:
			if arr[i] == 'A':
				ans = max(i - k + 1, ans)
			elif arr[i] == 'O' and j < m:
				ans = max(i - k + 1, ans)
				j = j + 1
			else:
				while arr[k] == 'A':
					k = k + 1
				k = k + 1
			i = i + 1
		return ans


class Solution:

	def appleSequences(self, n, m, arr):
		(r, l) = (0, 0)
		ans = 0
		while r < n:
			if arr[r] == 'A':
				r += 1
			elif m > 0:
				r += 1
				m -= 1
			else:
				ans = max(ans, r - l)
				while arr[l] != 'O':
					l += 1
				l += 1
				m += 1
		ans = max(ans, r - l)
		return ans


class Solution:

	def appleSequences(self, n, m, arr):
		if arr.count('O') <= m:
			return n
		a = [-1]
		for i in range(n):
			if arr[i] == 'O':
				a.append(i)
		a.append(int(n))
		ans = 0
		m += 1
		for i in range(len(a) - m):
			curr = a[i + m] - a[i] - 1
			ans = max(ans, curr)
		return ans


class Solution:

	def appleSequences(self, n, m, arr):
		end = 0
		start = 0
		c = 0
		ma = 0
		while end < n:
			if arr[end] == 'O':
				c += 1
			while start < n and c > m:
				if arr[start] == 'O':
					c -= 1
				start += 1
			ma = max(ma, end - start + 1)
			end += 1
		return ma