Notes:

*Code must be written in C Language/ UBUNTU environment.

*To get full credit for the question, you need to provide a brief explanation of your code and the efficiency analysis with comments.

*Also, you need to provide the proof for the correctness of the algorithm with comments.

3. Given an array of size n that has the following specifications: (i) each element in the array contains either a policeman or a thief, (ii) each policeman can catch only one thief, (iii) a policeman cannot catch a thief who is more than k units away from the policeman. Devise a greedy algorithm that takes a sequence of n characters consisting of 'P' and 'T' and an integer value k as input, and outputs the maximum number of thieves that can be caught. All the inputs given to the algorithm are assumed to be legitimate, i.e. the users are assumed to provide only the characters 'P' and 'K' for the sequence, and an integer value k. For the array [P, T, T, P, T ] and k = 1, your algorithm should output 2 For the array [T, T, P, P, T, P ] and k = 2, your algorithm should output 3