Given an array of size n such that each element contains either a 'P' for policeman or a 'T' for thief. Find the maximum number of thieves that can be caught by the police. 
Keep in mind the following conditions :
	Each policeman can catch only one thief.
	A policeman cannot catch a thief who is more than K units away from him.
Example 1:
Input:
N = 5, K = 1
arr[] = {P, T, T, P, T}
Output: 2
Explanation: Maximum 2 thieves can be 
caught. First policeman catches first thief 
and second police man can catch either second 
or third thief.
Example 2:
Input:
N = 6, K = 2
arr[] = {T, T, P, P, T, P}
Output: 3
Explanation: Maximum 3 thieves can be caught.
Your Task:  
You dont need to read input or print anything. Complete the function catchThieves() that takes n, k and arr[ ] as input parameters and returns the maximum number of thieves that can be caught by the police. 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ n ≤ 10^{5}
1 ≤ k ≤ 100
arr[i] = 'P' or 'T'

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Greedy algorithms

Starter code: #User function Template for python3



class Solution:

    def catchThieves(self, arr, n, k): 

        # code here 

Solutions:
class Solution:

	def catchThieves(self, arr, n, k):
		(theifs, police) = ([], [])
		for i in range(len(arr)):
			if arr[i] == 'T':
				theifs.append(i)
			else:
				police.append(i)
		co = 0
		(i, j) = (0, 0)
		while i < len(police) and j < len(theifs):
			if abs(police[i] - theifs[j]) <= k:
				co += 1
				i += 1
				j += 1
			elif police[i] < theifs[j]:
				i += 1
			else:
				j += 1
		return co


class Solution:

	def catchThieves(self, arr, n, k):
		police = []
		thieves = []
		count = 0
		for (index, person) in enumerate(arr):
			if person == 'P':
				police.append(index)
			else:
				thieves.append(index)
		p1 = 0
		p2 = 0
		while p1 < len(police) and p2 < len(thieves):
			if abs(police[p1] - thieves[p2]) <= k:
				p1 += 1
				p2 += 1
				count += 1
			elif thieves[p2] > police[p1]:
				p1 += 1
			else:
				p2 += 1
		return count


class Solution:

	def catchThieves(self, arr, n, k):
		t = []
		p = []
		ans = 0
		for i in range(n):
			if arr[i] == 'P':
				p.append(i)
			elif arr[i] == 'T':
				t.append(i)
		i = j = 0
		while i < len(p) and j < len(t):
			if abs(p[i] - t[j]) <= k:
				ans += 1
				i += 1
				j += 1
			elif p[i] < t[j]:
				i += 1
			else:
				j += 1
		return ans


class Solution:

	def catchThieves(self, arr, n, k):
		t = 0
		cnt = 0
		for i in range(n):
			if arr[i] == 'T':
				continue
			winSt = max(0, i - k)
			winEnd = min(n - 1, i + k)
			while t < winSt:
				t += 1
			while t <= winEnd:
				if arr[t] == 'T':
					cnt += 1
					t += 1
					break
				t += 1
		return cnt


class Solution:

	def catchThieves(self, arr, n, k):
		ans = 0
		last_thief = 0
		for i in range(n):
			if arr[i] == 'P':
				if last_thief < i - k:
					ini = i - k
				else:
					ini = last_thief
				final = i + k
				for x in range(ini, final + 1):
					if x < n and arr[x] == 'T':
						arr[x] = '-'
						ans += 1
						last_thief = x
						break
					elif x == n:
						break
		return ans


class Solution:

	def catchThieves(self, lis, n, k):
		policlis = [i for i in range(len(lis)) if lis[i] == 'P']
		thieflis = [i for i in range(len(lis)) if lis[i] == 'T']
		(pptr, tptr) = (0, 0)
		ans = 0
		while pptr < len(policlis) and tptr < len(thieflis):
			if abs(policlis[pptr] - thieflis[tptr]) <= k:
				ans += 1
				pptr += 1
				tptr += 1
			elif policlis[pptr] < thieflis[tptr]:
				pptr += 1
			else:
				tptr += 1
		return ans


class Solution:

	def catchThieves(self, arr, n, k):
		i = 0
		l = 0
		r = 0
		res = 0
		thi = []
		pol = []
		while i < n:
			if arr[i] == 'P':
				pol.append(i)
			elif arr[i] == 'T':
				thi.append(i)
			i += 1
		while l < len(thi) and r < len(pol):
			if abs(thi[l] - pol[r]) <= k:
				res += 1
				l += 1
				r += 1
			elif thi[l] < pol[r]:
				l += 1
			else:
				r += 1
		return res


class Solution:

	def catchThieves(self, A, n, k):
		caught = [False] * len(A)
		i = j = 0
		while j < len(A):
			if caught[i]:
				i += 1
			elif j - i < k and A[i] == A[j]:
				j += 1
			else:
				caught[j] = A[i] != A[j]
				i += 1
				j += 1
		return sum(caught)


class Solution:

	def catchThieves(self, arr, n, k):
		t = 0
		p = 0
		ans = 0
		while p < n and t < n:
			while p < n and arr[p] != 'P':
				p += 1
			while t < n and arr[t] != 'T':
				t += 1
			if p < n and t < n and (abs(p - t) <= k):
				ans += 1
				p += 1
				t += 1
			elif p < n and t < n and (p - t > k):
				t += 1
			elif p < n and t < n and (t - p > k):
				p += 1
		return ans


class Solution:

	def catchThieves(self, arr, n, k):
		count = 0
		for i in range(n - 1):
			if arr[i] == 'P':
				for j in range(i + 1, i + k + 1):
					if j < n:
						if arr[j] == 'T':
							count += 1
							arr[j] = 1
							break
					else:
						break
			elif arr[i] == 'T':
				for j in range(i + 1, i + k + 1):
					if j < n:
						if arr[j] == 'P':
							count += 1
							arr[j] = 1
							break
					else:
						break
		return count


class Solution:

	def catchThieves(self, arr, n, k):
		policemen = [i for i in range(n) if arr[i] == 'P']
		thieves = [i for i in range(n) if arr[i] == 'T']
		(p, t) = (0, 0)
		g = 0
		while p < len(policemen) and t < len(thieves):
			if abs(policemen[p] - thieves[t]) <= k:
				g += 1
				p += 1
				t += 1
			elif thieves[t] < policemen[p]:
				t += 1
			else:
				p += 1
		return g


class Solution:

	def catchThieves(self, arr, n, k):
		pols = []
		thie = []
		for (idx, i) in enumerate(arr):
			if i == 'P':
				pols.append(idx)
			else:
				thie.append(idx)
		l = r = res = 0
		while l < len(pols) and r < len(thie):
			if abs(pols[l] - thie[r]) <= k:
				res += 1
				l += 1
				r += 1
			elif pols[l] < thie[r]:
				l += 1
			else:
				r += 1
		return res


class Solution:

	def catchThieves(self, arr, n, k):
		sol = 0
		for i in range(n):
			if arr[i] == 'P':
				for j in range(i, i + k + 1):
					if n > j and arr[j] == 'T':
						sol += 1
						arr[j] = None
						break
			elif arr[i] == 'T':
				for j in range(i, i + k + 1):
					if n > j and arr[j] == 'P':
						sol += 1
						arr[j] = None
						break
		return sol


class Solution:

	def catchThieves(self, arr, n, k):
		(ind, res, last_caught, t) = (0, 0, 0, 0)
		while ind < n:
			if arr[ind] == 'P':
				(lower_limit, upper_limit) = (ind - k, ind + k)
				if lower_limit <= last_caught:
					if last_caught != 0 or t:
						lower_limit = last_caught + 1
					else:
						lower_limit = last_caught
						t = 1
				if upper_limit >= n:
					upper_limit = n - 1
				dup = lower_limit
				for x in arr[lower_limit:upper_limit + 1]:
					if x == 'T':
						last_caught = dup
						res += 1
						break
					dup += 1
			ind += 1
		return res


class Solution:

	def catchThieves(self, arr, n, k):
		police = []
		thief = []
		for i in range(n):
			if arr[i] == 'P':
				police.append(i)
			else:
				thief.append(i)
		(i, j) = (0, 0)
		count = 0
		while i < len(police) and j < len(thief):
			if abs(police[i] - thief[j]) <= k:
				count += 1
				i += 1
				j += 1
			elif police[i] > thief[j]:
				j += 1
			else:
				i += 1
		return count


class Solution:

	def catchThieves(self, arr, n, k):
		pol = []
		the = []
		for i in range(n):
			if arr[i] == 'P':
				pol.append(i)
			else:
				the.append(i)
		l = r = 0
		res = 0
		while l < len(pol) and r < len(the):
			if abs(pol[l] - the[r]) <= k:
				res += 1
				l += 1
				r += 1
			elif the[r] < pol[l]:
				r += 1
			else:
				l += 1
		return res


class Solution:

	def catchThieves(self, arr, n, k):
		theives = []
		police = []
		for i in range(n):
			if arr[i] == 'T':
				theives.append(i)
			else:
				police.append(i)
		j = 0
		count = 0
		i = 0
		while i < len(police) and j < len(theives):
			diff = 0
			if police[i] > theives[j]:
				diff = police[i] - theives[j]
				if diff <= k:
					count += 1
					i += 1
					j += 1
				else:
					j += 1
			else:
				diff = theives[j] - police[i]
				if diff <= k:
					count += 1
					i += 1
					j += 1
				else:
					i += 1
		return count


class Solution:

	def catchThieves(self, arr, n, k):
		(tf, pl, res) = (-1, -1, 0)
		for i in range(n):
			if tf != -1 and pl != -1:
				break
			if tf == -1 and arr[i] == 'T':
				tf = i
			if pl == -1 and arr[i] == 'P':
				pl = i
		if tf == -1 or pl == -1:
			return res
		while tf < n and pl < n:
			if abs(pl - tf) <= k:
				res += 1
				pl += 1
				tf += 1
				while pl < n and arr[pl] != 'P':
					pl += 1
				while tf < n and arr[tf] != 'T':
					tf += 1
			elif pl < tf:
				pl += 1
				while pl < n and arr[pl] != 'P':
					pl += 1
			else:
				tf += 1
				while tf < n and arr[tf] != 'T':
					tf += 1
		return res


class Solution:

	def catchThieves(self, arr, n, k):
		pol = []
		thi = []
		for i in range(n):
			if arr[i] == 'P':
				pol.append(i)
			else:
				thi.append(i)
		if len(pol) == 0 or len(thi) == 0:
			return 0
		p_idx = 0
		t_idx = 0
		result = 0
		while p_idx < len(pol) and t_idx < len(thi):
			if abs(pol[p_idx] - thi[t_idx]) <= k:
				result += 1
				p_idx += 1
				t_idx += 1
			elif pol[p_idx] < thi[t_idx]:
				p_idx += 1
			else:
				t_idx += 1
		return result


from collections import deque

class Solution:

	def catchThieves(self, arr, n, k):
		queue = deque([], maxlen=k)
		count = 0
		for item in arr:
			while queue and queue[0] == None:
				queue.popleft()
			if item == 'P' and queue and (queue[0] == 'T'):
				count += 1
				queue.popleft()
				queue.append(None)
			elif item == 'T' and queue and (queue[0] == 'P'):
				count += 1
				queue.popleft()
				queue.append(None)
			else:
				queue.append(item)
		return count


class Solution:

	def catchThieves(self, arr, n, k):
		thivesPos = []
		policePos = []
		for itr in range(len(arr)):
			if arr[itr] == 'P':
				policePos.append(itr)
			else:
				thivesPos.append(itr)
		thivesCaught = 0
		p = t = 0
		while p < len(policePos) and t < len(thivesPos):
			if abs(policePos[p] - thivesPos[t]) <= k:
				thivesCaught += 1
				t += 1
				p += 1
			elif policePos[p] > thivesPos[t]:
				t += 1
			else:
				p += 1
		return thivesCaught


class Solution:

	def catchThieves(self, arr, n, k):
		(Pol, Thi) = ([], [])
		count = 0
		for i in range(n):
			if arr[i] == 'P':
				Pol.append(i)
			else:
				Thi.append(i)
		(i, j) = (0, 0)
		while i < len(Pol) and j < len(Thi):
			distance = abs(Pol[i] - Thi[j])
			if distance <= k:
				count += 1
				i += 1
				j += 1
			elif Pol[i] > Thi[j]:
				j += 1
			else:
				i += 1
		return count


class Solution:

	def catchThieves(self, arr, n, k):
		(t, p) = ([], [])
		for i in range(n):
			if arr[i] == 'P':
				p.append(i)
			else:
				t.append(i)
		count = 0
		(t_pointer, p_pointer) = (0, 0)
		while t_pointer < len(t) and p_pointer < len(p):
			d = abs(t[t_pointer] - p[p_pointer])
			if d <= k:
				count += 1
				t_pointer += 1
				p_pointer += 1
			elif t[t_pointer] > p[p_pointer]:
				p_pointer += 1
			else:
				t_pointer += 1
		return count


class Solution:

	def catchThieves(self, arr, n, k):
		police = []
		thief = []
		for (i, x) in enumerate(arr):
			if x == 'P':
				police.append(i)
			else:
				thief.append(i)
		(i, j, res) = (0, 0, 0)
		while i < len(police) and j < len(thief):
			if abs(police[i] - thief[j]) <= k:
				res += 1
				i += 1
				j += 1
			elif police[i] > thief[j]:
				j += 1
			else:
				i += 1
		return res


class Solution:

	def catchThieves(self, arr, n, k):
		count = 0
		pol = -1
		thi = -1
		for i in range(n):
			if arr[i] == 'P':
				pol = i
				break
		for i in range(n):
			if arr[i] == 'T':
				thi = i
				break
		while pol == -1 or thi == -1:
			return 0
		while pol < n and thi < n:
			distance = abs(pol - thi)
			if distance <= k:
				count += 1
				pol += 1
				thi += 1
				while pol < n and arr[pol] == 'T':
					pol += 1
				while thi < n and arr[thi] == 'P':
					thi += 1
			elif thi > pol:
				pol += 1
				while pol < n and arr[pol] == 'T':
					pol += 1
			else:
				thi += 1
				while thi < n and arr[thi] == 'P':
					thi += 1
		return count


from collections import deque

class Solution:

	def catchThieves(self, arr, n, k):

		def findNextP(start):
			nonlocal n
			for i in range(start + 1, n):
				if arr[i] == 'P':
					return i
			return -1

		def findNextT(start):
			nonlocal n
			for i in range(start + 1, n):
				if arr[i] == 'T':
					return i
			return -1
		pi = findNextP(-1)
		ti = findNextT(-1)
		cnt = 0
		while pi < n and ti < n:
			if pi == -1 or ti == -1:
				break
			if abs(pi - ti) <= k:
				pi = findNextP(pi)
				ti = findNextT(ti)
				cnt += 1
			elif pi < ti:
				pi = findNextP(pi)
			else:
				ti = findNextT(ti)
		return cnt


from collections import deque

class Solution:

	def catchThieves(self, arr, n, k):
		pqueue = deque()
		tqueue = deque()
		cnt = 0
		for i in range(n):
			if arr[i] == 'P':
				pqueue.append(i)
			else:
				tqueue.append(i)
			while tqueue and pqueue:
				leftMostThiefPos = tqueue[0]
				leftMostPolicePos = pqueue[0]
				if abs(leftMostThiefPos - leftMostPolicePos) <= k:
					tqueue.popleft()
					pqueue.popleft()
					cnt += 1
					break
				elif arr[i] == 'P':
					tqueue.popleft()
				else:
					pqueue.popleft()
		return cnt


class Solution:

	def catchThieves(self, arr, n, k):
		thieves = []
		police = []
		for i in range(n):
			if arr[i] == 'T':
				thieves.append(i)
			else:
				police.append(i)
		if len(thieves) == 0 or len(police) == 0:
			return 0
		(t_i, p_i) = (0, 0)
		res = 0
		while t_i < len(thieves) and p_i < len(police):
			dist = abs(thieves[t_i] - police[p_i])
			if dist <= k:
				res += 1
				t_i += 1
				p_i += 1
			elif thieves[t_i] > police[p_i]:
				p_i += 1
			else:
				t_i += 1
		return res


class Solution:

	def catchThieves(self, arr, n, k):
		c = 0
		(p, t) = ([], [])
		for i in range(n):
			if arr[i] == 'P':
				p.append(i)
			else:
				t.append(i)
		(l, r) = (0, 0)
		while l < len(p) and r < len(t):
			if abs(p[l] - t[r]) <= k:
				c += 1
				l += 1
				r += 1
			elif p[l] < t[r]:
				l += 1
			else:
				r += 1
		return c


class Solution:

	def catchThieves(self, arr, n, k):
		(p, t) = ([], [])
		c = 0
		for (i, v) in enumerate(arr):
			if v == 'T':
				while len(p) > 0 and p[0] < i - k:
					p.pop(0)
				if len(p) > 0 and p[0] >= i - k and (p[0] <= i + k):
					c += 1
					p.pop(0)
				else:
					t.append(i)
			if v == 'P':
				while len(t) > 0 and t[0] < i - k:
					t.pop(0)
				if len(t) > 0 and t[0] >= i - k and (t[0] <= i + k):
					c += 1
					t.pop(0)
				else:
					p.append(i)
		return c


from collections import deque

class Solution:

	def catchThieves(self, arr, n, k):
		(p, t) = (deque([]), deque([]))
		ans = 0
		for i in range(n):
			while t and i - t[0] > k:
				t.popleft()
			while p and i - p[0] > k:
				p.popleft()
			if arr[i] == 'T':
				if p:
					ans += 1
					p.popleft()
				else:
					t.append(i)
			elif arr[i] == 'P':
				if t:
					ans += 1
					t.popleft()
				else:
					p.append(i)
		return ans


class Solution:

	def catchThieves(self, arr, n, k):
		polices = []
		thieves = []
		for i in range(n):
			if arr[i] == 'P':
				polices.append(i)
			else:
				thieves.append(i)
		i = 0
		j = 0
		catch = 0
		while i < len(polices) and j < len(thieves):
			if abs(polices[i] - thieves[j]) <= k:
				i += 1
				j += 1
				catch += 1
			elif polices[i] > thieves[j]:
				j += 1
			else:
				i += 1
		return catch


class Solution:

	def catchThieves(self, arr, n, k):
		(pl, th) = ([], [])
		for i in range(n):
			if arr[i] == 'P':
				pl.append(i)
			else:
				th.append(i)
		(p, t) = (0, 0)
		cnt = 0
		while p < len(pl) and t < len(th):
			if abs(pl[p] - th[t]) <= k:
				p += 1
				t += 1
				cnt += 1
			elif th[t] < pl[p]:
				t += 1
			else:
				p += 1
		return cnt


class Solution:

	def catchThieves(self, arr, n, k):
		pol = []
		thi = []
		for i in range(n):
			if arr[i] == 'T':
				thi.append(i)
			if arr[i] == 'P':
				pol.append(i)
		l = h = 0
		ans = 0
		while l < len(pol) and h < len(thi):
			if abs(pol[l] - thi[h]) <= k:
				ans += 1
				l += 1
				h += 1
			elif pol[l] > thi[h]:
				h += 1
			else:
				l += 1
		return ans


class Solution:

	def catchThieves(self, arr, n, k):
		Pidx = []
		res = 0
		for (i, c) in enumerate(arr):
			if c == 'P':
				Pidx.append(i)
		(l1, l2) = (0, 0)
		while l2 < len(arr):
			if arr[l2] == 'P':
				l2 += 1
			elif l1 == len(Pidx):
				return res
			elif l2 < Pidx[l1] and Pidx[l1] - l2 > k:
				l2 += 1
			elif l2 > Pidx[l1] and l2 - Pidx[l1] > k:
				l1 += 1
			else:
				res += 1
				l1 += 1
				l2 += 1
		return res


class Solution:

	def catchThieves(self, arr, n, k):
		st = []
		pl = []
		c = 0
		l = 0
		i = 0
		f = False
		for i in range(n):
			if arr[i] == 'P' or f:
				while st and st[0] < i - k:
					c += 1
					del st[0]
				if st:
					del st[0]
				else:
					pl.append(i)
			else:
				l += 1
				while pl and pl[0] < i - k:
					del pl[0]
				if not pl:
					st.append(i)
				else:
					del pl[0]
		return l - c - len(st)


class Solution:

	def catchThieves(self, arr, n, k):
		polices = []
		thieves = []
		for i in range(len(arr)):
			if arr[i] == 'P':
				polices.append(i)
			else:
				thieves.append(i)
		cp = len(polices)
		ct = len(thieves)
		pi = 0
		ti = 0
		count = 0
		while pi < cp and ti < ct:
			if abs(polices[pi] - thieves[ti]) <= k:
				pi += 1
				ti += 1
				count += 1
			elif thieves[ti] < polices[pi]:
				ti += 1
			else:
				pi += 1
		return count


class Solution:

	def catchThieves(self, arr, n, k):
		left = 0
		right = 0
		count = 0
		police = []
		thieve = []
		for index in range(n):
			if arr[index] == 'P':
				police.append(index)
			if arr[index] == 'T':
				thieve.append(index)
		while left < len(thieve) and right < len(police):
			if abs(thieve[left] - police[right]) <= k:
				count += 1
				left += 1
				right += 1
			elif thieve[left] < police[right]:
				left += 1
			else:
				right += 1
		return count


class Solution:

	def catchThieves(self, arr, n, k):
		i = 0
		res = 0
		l = 0
		r = 0
		polic = []
		thief = []
		while i in range(len(arr)):
			if arr[i] == 'P':
				polic.append(i)
			elif arr[i] == 'T':
				thief.append(i)
			i += 1
		while l < len(thief) and r < len(polic):
			if abs(thief[l] - polic[r]) <= k:
				res += 1
				l += 1
				r += 1
			elif thief[l] < polic[r]:
				l += 1
			else:
				r += 1
		return res


class Solution:

	def catchThieves(self, arr, n, k):
		thieves = []
		police = []
		for i in range(n):
			if arr[i] == 'T':
				thieves.append(i)
			else:
				police.append(i)
		(i, j) = (0, 0)
		count = 0
		while i < len(thieves) and j < len(police):
			distance = abs(thieves[i] - police[j])
			if distance <= k:
				count += 1
				i += 1
				j += 1
			elif thieves[i] > police[j]:
				j += 1
			else:
				i += 1
		return count


class Solution:

	def catchThieves(self, arr, n, k):
		cnt = thief = police = 0
		while thief < n and police < n:
			while thief < n and arr[thief] != 'T':
				thief += 1
			while police < n and arr[police] != 'P':
				police += 1
			if police < n and thief < n and (abs(police - thief) <= k):
				cnt += 1
				police += 1
				thief += 1
			elif thief < police:
				thief += 1
			else:
				police += 1
		return cnt


class Solution:

	def catchThieves(self, arr, n, k):
		police = []
		theft = []
		t = 0
		p = 0
		res = 0
		for i in range(n):
			if arr[i] == 'P':
				police.append(i)
			else:
				theft.append(i)
		while t < len(theft) and p < len(police):
			if abs(theft[t] - police[p]) <= k:
				res += 1
				t += 1
				p += 1
			elif theft[t] < police[p]:
				t += 1
			else:
				p += 1
		return res


class Solution:

	def catchThieves(self, arr, n, k):
		i = 0
		l = 0
		r = 0
		result = 0
		thief = []
		police = []
		while i < n:
			if arr[i] == 'P':
				police.append(i)
			elif arr[i] == 'T':
				thief.append(i)
			i += 1
		while l < len(thief) and r < len(police):
			if abs(thief[l] - police[r]) <= k:
				result += 1
				l += 1
				r += 1
			elif thief[l] < police[r]:
				l += 1
			else:
				r += 1
		return result


class Solution:

	def catchThieves(self, arr, n, k):
		start = []
		end = []
		ind = []
		for i in range(n):
			if arr[i] is 'P':
				start.append(i - k)
			else:
				ind.append(i)
		start = sorted(start)
		for i in start:
			end.append(min(i + 2 * k, n - 1))
		s = 0
		o = 0
		g = 0
		while g < len(ind) and o < len(start):
			if ind[g] > end[o]:
				o = o + 1
			elif ind[g] < start[o]:
				g = g + 1
			else:
				o = o + 1
				g = g + 1
				s = s + 1
		return s


class Solution:

	def catchThieves(self, arr, n, k):
		p = []
		t = []
		for i in range(n):
			if arr[i] == 'P':
				p.append(i)
			else:
				t.append(i)
		(x, y) = (0, 0)
		count = 0
		while x < len(p) and y < len(t):
			if abs(p[x] - t[y]) <= k:
				x += 1
				y += 1
				count += 1
			elif t[y] < p[x]:
				y += 1
			else:
				x += 1
		return count


class Solution:

	def catchThieves(self, arr, n, k):
		police_arr = []
		thieves_arr = []
		for i in range(n):
			if arr[i] == 'P':
				police_arr.append(i)
			else:
				thieves_arr.append(i)
		ans1 = 0
		i = 0
		r = 0
		while i < len(thieves_arr) and r < len(police_arr):
			if abs(thieves_arr[i] - police_arr[r]) <= k:
				ans1 += 1
				i += 1
				r += 1
			elif thieves_arr[i] < police_arr[r]:
				i += 1
			else:
				r += 1
		return ans1


class Solution:

	def catchThieves(self, A, n, k):

		def _find_next_T(j):
			return next((i for i in range(j, n) if A[i] == 'T'), n)

		def _get(i):
			return 'X' if i < 0 or i >= n else A[i]
		ans = 0
		tc = len([v for v in A[:k + 1] if v == 'T'])
		j = _find_next_T(0)
		for i in range(n):
			if A[i] == 'P' and tc > 0:
				ans += 1
				tc -= 1
				if j < i - k:
					j = _find_next_T(i - k)
				A[j] = 'X'
				j = _find_next_T(j + 1)
			(vl, vr) = (_get(i - k), _get(i + k + 1))
			if vl == 'T':
				tc -= 1
			if vr == 'T':
				tc += 1
		return ans


class Solution:

	def catchThieves(self, arr, n, k):
		(cop, chor) = ([], [])
		for i in range(n):
			if arr[i] == 'P':
				cop.append(i)
			elif arr[i] == 'T':
				chor.append(i)
		(p, t) = (0, 0)
		caught = 0
		while p < len(cop) and t < len(chor):
			if abs(cop[p] - chor[t]) <= k:
				caught += 1
				p += 1
				t += 1
			elif cop[p] < chor[t]:
				p += 1
			elif cop[p] > chor[t]:
				t += 1
		return caught


class Solution:

	def catchThieves(self, arr, n, k):
		caught = [False] * n
		thieves = []
		police = []
		count = 0
		for i in range(n):
			if arr[i] == 'T':
				if len(police) == 0:
					thieves.append(i)
				else:
					idx_police = police.pop(0)
					while i - idx_police > k and len(police) > 0:
						idx_police = police.pop(0)
					if abs(idx_police - i) <= k:
						count += 1
					else:
						thieves.append(i)
			elif len(thieves) == 0:
				police.append(i)
			else:
				idx_thieves = thieves.pop(0)
				while i - idx_thieves > k and len(thieves) > 0:
					idx_thieves = thieves.pop(0)
				if abs(idx_thieves - i) <= k:
					count += 1
				else:
					police.append(i)
		return count


from collections import deque

class Solution:

	def catchThieves(self, arr, n, k):
		p = []
		t = []
		for i in range(n):
			if arr[i] == 'P':
				p.append(i)
			else:
				t.append(i)
		tt = 0
		pp = 0
		ans = 0
		while tt < len(t) and pp < len(p):
			if abs(t[tt] - p[pp]) <= k:
				ans += 1
				tt += 1
				pp += 1
			elif t[tt] > p[pp]:
				pp += 1
			else:
				tt += 1
		return ans


class Solution:

	def catchThieves(self, A, N, K):
		T = []
		P = []
		for i in range(N):
			if A[i] == 'P':
				P.append(i)
			else:
				T.append(i)
		i = 0
		j = 0
		ans = 0
		while i < len(P) and j < len(T):
			if abs(P[i] - T[j]) <= K:
				ans += 1
				i += 1
				j += 1
			elif T[j] > P[i]:
				i += 1
			else:
				j += 1
		return ans


class Solution:

	def catchThieves(self, arr, n, k):
		pArr = []
		tArr = []
		for i in range(len(arr)):
			val = arr[i]
			if val == 'T':
				tArr.append(i)
			else:
				pArr.append(i)
		tArr.sort()
		pArr.sort()
		ans = 0
		(i, j) = (0, 0)
		while i < len(tArr) and j < len(pArr):
			if abs(tArr[i] - pArr[j]) <= k:
				ans += 1
				i += 1
				j += 1
			elif tArr[i] < pArr[j]:
				i += 1
			else:
				j += 1
		return ans


class Solution:

	def catchThieves(self, arr, n, k):
		p = []
		t = []
		for i in range(len(arr)):
			if arr[i] == 'P':
				p.append(i)
			else:
				t.append(i)
		ct = 0
		l_p = 0
		l_t = 0
		while l_p < len(p) and l_t < len(t):
			if abs(p[l_p] - t[l_t]) <= k:
				l_p += 1
				l_t += 1
				ct += 1
			elif p[l_p] > t[l_t]:
				l_t += 1
			else:
				l_p += 1
		return ct


class Solution:

	def catchThieves(self, arr, n, k):
		copsIndex = []
		tIndex = []
		for i in range(n):
			if arr[i] == 'P':
				copsIndex.append(i)
			else:
				tIndex.append(i)
		ans = 0
		while len(tIndex) > 0 and len(copsIndex) > 0:
			maxCopIndex = copsIndex[-1]
			maxThiefIndex = tIndex[-1]
			if abs(maxCopIndex - maxThiefIndex) <= k:
				ans += 1
				copsIndex.pop()
				tIndex.pop()
			elif maxCopIndex > maxThiefIndex:
				del copsIndex[-1]
			else:
				del tIndex[-1]
		return ans


class Solution:

	def catchThieves(self, nums, n, k):
		ans = 0
		(p, c) = (float('inf'), float('inf'))
		for i in range(len(nums)):
			if nums[i] == 'P':
				if p == float('inf'):
					p = i
			elif c == float('inf'):
				c = i
			if p != float('inf') and c != float('inf'):
				break
		while p < len(nums) and c < len(nums):
			if abs(p - c) <= k:
				ans += 1
				p += 1
				c += 1
				while p < len(nums) and nums[p] != 'P':
					p += 1
				while c < len(nums) and nums[c] != 'T':
					c += 1
			elif p < c:
				p += 1
				while p < len(nums) and nums[p] != 'P':
					p += 1
			else:
				c += 1
				while c < len(nums) and nums[c] != 'T':
					c += 1
		return ans