title: Policemen Catch Thieves
signature: function policemen_catch_thieves(arr, n, 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.test_code: 
  
  -- SOLUTION CODE
  -- ============================================
  PLACEHOLDER_CODE_BODY
  
  -- TESTING CODE 
  -- ============================================
  function isCorrect(actual, expected)
      if type(expected) ~= type(actual) then
          return false
      end
      
      if type(expected) == 'table' then
          for k,v_expected in pairs(expected) do
              
              if actual[k] == nil then
                  return false
              end
              local v_actual = actual[k]
              if not isCorrect(v_actual, v_expected) then
                  return false
              end
              actual[k]=nil
          end
      
          if next(actual) then 
              return false
          end
          return true
      else
          return actual == expected
      end
  end
  
  function validateSolution(actual, expected)
      return isCorrect(actual,expected)
  end
  
  function driver(arr, n, k, expected)
      local exec_result;
      local status, error_msg = pcall(function () 
          exec_result=PLACEHOLDER_FN_NAME(arr, n, k) 
      end)
      if status then
          if validateSolution(exec_result,expected) then
              return "PASSED"
          end
          return "FAILED"
      else
          return string.format("ERROR=%s",string.gsub(error_msg,".*:[%d]+: ",""))
      end
  end
      
  function main()
      result = driver({'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)
      print(string.format("TEST-0...%s",result))
  
      result = driver({'7', '6', '0', '1', '0', '1'}, 3, 3, 0)
      print(string.format("TEST-1...%s",result))
  
      result = driver({'0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1'}, 9, 10, 0)
      print(string.format("TEST-2...%s",result))
  
      result = driver({'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)
      print(string.format("TEST-3...%s",result))
  
      result = driver({'1', '1', '5', '8', '8'}, 2, 2, 0)
      print(string.format("TEST-4...%s",result))
  
      result = driver({'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)
      print(string.format("TEST-5...%s",result))
  
      result = driver({'A', 'I', 'K', 'Q', 'Q', 'X', 'Z', 'f', 'g'}, 5, 8, 0)
      print(string.format("TEST-6...%s",result))
  
      result = driver({'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)
      print(string.format("TEST-7...%s",result))
  
      result = driver({'0', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1'}, 8, 10, 0)
      print(string.format("TEST-8...%s",result))
  
      result = driver({'D', 'C', 'P', 'H', 'G', 'o', 'u', 'P', 'T', 'G', 'E', 'U', 'n', 'E', 'U'}, 11, 12, 1)
      print(string.format("TEST-9...%s",result))
  
  end
  
  main()
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.extension: lua
question_info.entry_fn_name: policemen_catch_thieves
question_info.test_case_ids: 0 1 2 3 4 5 6 7 8 9
question_info.commands: lua __FILENAME__