Policemen catch thieves | Returns maximum number of thieves that can be caught . ; store indices in list ; track lowest current indices of thief : thi [ l ] , police : pol [ r ] ; can be caught ; increment the minimum index ; Driver program
def policeThief ( arr , n , k ) : NEW_LINE INDENT i = 0 NEW_LINE l = 0 NEW_LINE r = 0 NEW_LINE res = 0 NEW_LINE thi = [ ] NEW_LINE pol = [ ] NEW_LINE while i < n : NEW_LINE INDENT if arr [ i ] == ' P ' : NEW_LINE INDENT pol . append ( i ) NEW_LINE DEDENT elif arr [ i ] == ' T ' : NEW_LINE INDENT thi . append ( i ) NEW_LINE DEDENT i += 1 NEW_LINE DEDENT while l < len ( thi ) and r < len ( pol ) : NEW_LINE INDENT if ( abs ( thi [ l ] - pol [ r ] ) <= k ) : NEW_LINE INDENT res += 1 NEW_LINE l += 1 NEW_LINE r += 1 NEW_LINE DEDENT elif thi [ l ] < pol [ r ] : NEW_LINE INDENT l += 1 NEW_LINE DEDENT else : NEW_LINE INDENT r += 1 NEW_LINE DEDENT DEDENT return res NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr1 = [ ' P ' , ' T ' , ' T ' , ' P ' , ' T ' ] NEW_LINE k = 2 NEW_LINE n = len ( arr1 ) NEW_LINE print ( ( " Maximum ▁ thieves ▁ caught : ▁ { } " . format ( policeThief ( arr1 , n , k ) ) ) ) NEW_LINE arr2 = [ ' T ' , ' T ' , ' P ' , ' P ' , ' T ' , ' P ' ] NEW_LINE k = 2 NEW_LINE n = len ( arr2 ) NEW_LINE print ( ( " Maximum ▁ thieves ▁ caught : ▁ { } " . format ( policeThief ( arr2 , n , k ) ) ) ) NEW_LINE arr3 = [ ' P ' , ' T ' , ' P ' , ' T ' , ' T ' , ' P ' ] NEW_LINE k = 3 NEW_LINE n = len ( arr3 ) NEW_LINE print ( ( " Maximum ▁ thieves ▁ caught : ▁ { } " . format ( policeThief ( arr3 , n , k ) ) ) ) NEW_LINE DEDENT