I came across this question today and found it interesting (it was mentioned somewhere that this question was asked in a Microsoft interview).

You are given an array of size n in which each element contains either a 'P' for policeman or a 'T' for thief and an integer value k. Maximize the number of thieves that can be caught by the police.
The constraints are :

• A police can catch at most one thief.
• A police cannot catch a thief who is more than K units away from him.

Input 1:

P T T P T T P
2

Output 1:

3

Input 2:

T T P P T P T P
2

Output 2:

4

There are two ways to catch a thief.
CASE 1: The thief to be caugth lies to the left of the police.
CASE 2: The thief to be caugth lies to the right of the police.

Mathematical expression for the above two cases:
Let index of police be i and index of the thief be j.
When j < i and i - j ≤ k we will choose the smallest possible j(farthest on the left).
When j > i and j - i ≤ k we will choose the smallest possible j(closest to the right).

For both conditions we will choose the leftmost thief possible to catch.

JAVA Code:

TC: O(N)
SC: O(N)

class Solution 
{ 
    int catchThieves(char arr[], int k) 
	{ 
        Queue<Integer> tq = new ArrayDeque<>(); // queue to store index of thief
        Queue<Integer> pq = new ArrayDeque<>(); // queue to store index of police
        
        for (int i = 0; i < n; i++) { // loop through array to find index of thief/police
            if (arr[i] == 'T') {
                tq.offer(i);
            } else {
                pq.offer(i);
            }
        }
        
		int counter = 0;
        while (!tq.isEmpty() && !pq.isEmpty()) {
            if (Math.abs(tq.peek() - pq.peek()) <= k) { // thief is within the reach of the policeman
                counter++;
                pq.poll();
                tq.poll();
            } else if (tq.peek() > pq.peek()) { // thief lies beyond the reach of the current policeman
                pq.poll();
            } else { // thief is not reachable from any of the police
                tq.poll();   
            }
        }
        
        return counter;
	} 
} 

Intuition:

Well my intuition is that whenever we encounter any policeman while looping from 0 to n, then the thief that can be caught should lie within the range i - k to i + k and if we catch the leftmost thief in this range who is not already been caught then we can make sure that for the next policeman next thief is as close to him as possible(probability of the next thief getting caught by next policeman increases).