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

2

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

Output

3