Police and Thieves Problem

Problem Summary

You are given an array containing:

'P' → Policeman
'T' → Thief

Each policeman can catch at most one thief, and only within a distance k.

Goal: Maximize number of thieves caught.

Key Idea

We use a two-pointer greedy approach:

One pointer for policemen
One pointer for thieves

We try to match the closest possible valid pairs.

Greedy Strategy

We maintain:

i → policeman pointer
j → thief pointer

Rules:

If distance ≤ k → match them
If policeman is too far left → move policeman
If thief is too far left → move thief

Intuition

We always want to:

Match the closest possible P-T pair

Why?

Greedy matching prevents wasting opportunities
Ensures maximum pairing

Step-by-Step Example

Input

arr = ['P','T','T','P','T'], k = 1

Process

P at 0 → T at 1 ✔ (caught)
P at 3 → T at 2 ✔ (caught)

Output

Algorithm

Collect positions of all policemen
Collect positions of all thieves
Use two pointers to match them greedily

Java Solution (Optimal O(n))

class Solution {
    public int catchThieves(char[] arr, int k) {
        int n = arr.length;

        int i = 0; // policeman pointer
        int j = 0; // thief pointer
        int count = 0;

        // traverse array
        while (i < n && j < n) {

            // move i to next P
            while (i < n && arr[i] != 'P') i++;

            // move j to next T
            while (j < n && arr[j] != 'T') j++;

            // if either reached end
            if (i >= n || j >= n) break;

            // check distance
            if (Math.abs(i - j) <= k) {
                count++;   // match found
                i++;
                j++;
            }
            else if (i < j) {
                i++; // policeman too left
            }
            else {
                j++; // thief too left
            }
        }

        return count;
    }
}

Complexity

Time: O(n)
Space: O(1)

Why This Works

Always pairs nearest valid P and T
Prevents wasting matches
Greedy ensures global optimum

Key Takeaways

Two pointers on sorted positions
Greedy matching strategy
Always match closest valid pair
Skip invalid pairs efficiently

Pattern Recognition

This problem belongs to:

Greedy algorithms
Two pointer technique
Matching problems
Interval-like constraints

Final Output Example

Input

['T','T','P','P','T','P'], k = 2