title: Policemen Catch Thieves
signature: class Solution {
  
      public Integer policemenCatchThieves(ArrayList<Character> arr, Integer n, Integer k) {
source_py: def policemen_catch_thieves(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
source_cpp: int policemen_catch_thieves(vector<char> arr, int n, int k) {
    int res = 0;
    vector < int > thi;
    vector < int > pol;
    for ( int i = 0;
    i < n;
    i ++ ) {
      if ( arr [ i ] == 'P' ) pol . push_back ( i );
      else if ( arr [ i ] == 'T' ) thi . push_back ( i );
    }
    int l = 0, r = 0;
    while ( l < thi . size ( ) && r < pol . size ( ) ) {
      if ( abs ( thi [ l ] - pol [ r ] ) <= k ) {
        res ++;
        l ++;
        r ++;
      }
      else if ( thi [ l ] < pol [ r ] ) l ++;
      else r ++;
    }
    return res;
  }
question_info.extension: java
question_info.entry_fn_name: policemenCatchThieves
question_info.entry_cls_name: Solution
question_info.test_list: [{"idx": 0, "outputs": 0, "inputs": {"arr": ["A", "B", "B", "D", "E", "E", "F", "G", "G", "G", "I", "J", "O", "P", "Q", "Q", "Q", "Q", "R", "R", "S", "U", "X", "Y", "Y", "c", "d", "h", "i", "i", "i", "i", "k", "k", "l", "l", "l", "l", "m", "p", "r", "r", "s", "t", "t", "u", "x", "z"], "n": 33, "k": 45}}, {"idx": 1, "outputs": 0, "inputs": {"arr": ["7", "6", "0", "1", "0", "1"], "n": 3, "k": 3}}, {"idx": 2, "outputs": 0, "inputs": {"arr": ["0", "0", "0", "0", "0", "0", "0", "0", "0", "1", "1", "1", "1", "1", "1", "1", "1", "1"], "n": 9, "k": 10}}, {"idx": 3, "outputs": 0, "inputs": {"arr": ["y", "k", "S", "i", "s", "r", "i", "z", "y", "f", "E", "U", "y", "G", "f", "f", "s", "v", "v", "D", "v", "V", "S", "D", "K", "S", "f", "V", "g", "I", "J", "p", "j", "k", "R", "n", "m", "O", "L", "X", "y", "U", "y", "k", "w"], "n": 24, "k": 44}}, {"idx": 4, "outputs": 0, "inputs": {"arr": ["1", "1", "5", "8", "8"], "n": 2, "k": 2}}, {"idx": 5, "outputs": 0, "inputs": {"arr": ["0", "1", "0", "0", "1", "1", "1", "0", "0", "0", "1", "0", "1", "0", "1", "0", "0", "0", "0", "0", "1", "0", "0", "0", "0", "1", "1", "1", "0", "0", "0", "0", "0", "0"], "n": 23, "k": 18}}, {"idx": 6, "outputs": 0, "inputs": {"arr": ["A", "I", "K", "Q", "Q", "X", "Z", "f", "g"], "n": 5, "k": 8}}, {"idx": 7, "outputs": 0, "inputs": {"arr": ["7", "0", "6", "9", "7", "5", "1", "3", "9", "8", "0", "0", "1", "3", "9", "2", "5", "5", "2", "7", "9", "3", "3", "9", "3", "8", "5", "5", "0", "4", "6", "2", "7", "4", "0", "4", "6", "4", "2", "3"], "n": 35, "k": 28}}, {"idx": 8, "outputs": 0, "inputs": {"arr": ["0", "0", "0", "1", "1", "1", "1", "1", "1", "1", "1"], "n": 8, "k": 10}}, {"idx": 9, "outputs": 1, "inputs": {"arr": ["D", "C", "P", "H", "G", "o", "u", "P", "T", "G", "E", "U", "n", "E", "U"], "n": 11, "k": 12}}]
question_info.test_code: import static java.util.Map.entry;  
  import java.util.*;
  import java.lang.*;
  // TESTING CODE 
  // ============================================
  class QuestionEvaluator {
      public static String validateSolution(ArrayList<Character> arr, Integer n, Integer k, Integer expected){
          try{
              Driver driver = new Driver();
              if (driver.run(arr, n, k,expected)){
                  return "PASSED";
              }
              return "FAILED";
              
          } catch (Exception exception_obj){
              return exception_obj.getClass().getSimpleName();
          }
  
      }
      public static void main(String[] args) {
          String result;
          result = validateSolution(new ArrayList<>(Arrays.asList('A', 'B', 'B', 'D', 'E', 'E', 'F', 'G', 'G', 'G', 'I', 'J', 'O', 'P', 'Q', 'Q', 'Q', 'Q', 'R', 'R', 'S', 'U', 'X', 'Y', 'Y', 'c', 'd', 'h', 'i', 'i', 'i', 'i', 'k', 'k', 'l', 'l', 'l', 'l', 'm', 'p', 'r', 'r', 's', 't', 't', 'u', 'x', 'z')), 33, 45, 0);
          System.out.println(String.format("%s%s","TEST-0...",result));    
      
          result = validateSolution(new ArrayList<>(Arrays.asList('7', '6', '0', '1', '0', '1')), 3, 3, 0);
          System.out.println(String.format("%s%s","TEST-1...",result));    
      
          result = validateSolution(new ArrayList<>(Arrays.asList('0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1')), 9, 10, 0);
          System.out.println(String.format("%s%s","TEST-2...",result));    
      
          result = validateSolution(new ArrayList<>(Arrays.asList('y', 'k', 'S', 'i', 's', 'r', 'i', 'z', 'y', 'f', 'E', 'U', 'y', 'G', 'f', 'f', 's', 'v', 'v', 'D', 'v', 'V', 'S', 'D', 'K', 'S', 'f', 'V', 'g', 'I', 'J', 'p', 'j', 'k', 'R', 'n', 'm', 'O', 'L', 'X', 'y', 'U', 'y', 'k', 'w')), 24, 44, 0);
          System.out.println(String.format("%s%s","TEST-3...",result));    
      
          result = validateSolution(new ArrayList<>(Arrays.asList('1', '1', '5', '8', '8')), 2, 2, 0);
          System.out.println(String.format("%s%s","TEST-4...",result));    
      
          result = validateSolution(new ArrayList<>(Arrays.asList('0', '1', '0', '0', '1', '1', '1', '0', '0', '0', '1', '0', '1', '0', '1', '0', '0', '0', '0', '0', '1', '0', '0', '0', '0', '1', '1', '1', '0', '0', '0', '0', '0', '0')), 23, 18, 0);
          System.out.println(String.format("%s%s","TEST-5...",result));    
      
          result = validateSolution(new ArrayList<>(Arrays.asList('A', 'I', 'K', 'Q', 'Q', 'X', 'Z', 'f', 'g')), 5, 8, 0);
          System.out.println(String.format("%s%s","TEST-6...",result));    
      
          result = validateSolution(new ArrayList<>(Arrays.asList('7', '0', '6', '9', '7', '5', '1', '3', '9', '8', '0', '0', '1', '3', '9', '2', '5', '5', '2', '7', '9', '3', '3', '9', '3', '8', '5', '5', '0', '4', '6', '2', '7', '4', '0', '4', '6', '4', '2', '3')), 35, 28, 0);
          System.out.println(String.format("%s%s","TEST-7...",result));    
      
          result = validateSolution(new ArrayList<>(Arrays.asList('0', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1')), 8, 10, 0);
          System.out.println(String.format("%s%s","TEST-8...",result));    
      
          result = validateSolution(new ArrayList<>(Arrays.asList('D', 'C', 'P', 'H', 'G', 'o', 'u', 'P', 'T', 'G', 'E', 'U', 'n', 'E', 'U')), 11, 12, 1);
          System.out.println(String.format("%s%s","TEST-9...",result));    
      
      }
  }
  
  class Driver{
      public boolean run(ArrayList<Character> arr, Integer n, Integer k, Integer expected){
  
          PLACEHOLDER_CLS_NAME sol = new PLACEHOLDER_CLS_NAME();
          return validateSolution(sol.PLACEHOLDER_FN_NAME(arr, n, k),expected);
      }
      
      public boolean validateSolution(Integer actual, Integer expected){
          return actual.equals(expected);
      }
  }
  
  
  // SOLUTION CODE
  // ============================================
  PLACEHOLDER_CODE_BODY
question_info.test_case_ids: 0 1 2 3 4 5 6 7 8 9
question_info.commands: java __FILENAME__