Minimum Number Of Lamps

Posted: 12 Nov, 2020
Difficulty: Easy


Try Problem

You are given a string 'S' containing dots(.) and asterisks(*) only, where the dot represents free spaces, and the asterisk denotes lamps. A lamp can lighten up its own cell as well as its immediate neighboring cells. You need to determine the minimum number of extra lamps that have to be installed at some free spaces in the string so that the whole string will be illuminated i.e. all the indices of the string can have access to the light of some lamp.

Note :
If a lamp is present at index 'I', then it illuminates index 'I' - 1, 'I' and 'I' + 1.

If a lamp is present at index 0, then it illuminates only 0 and 1.

Given that the length of the string is greater than or equal to 2.

If a lamp is present at the last index, then it illuminates the last and the second last index, given that the length of the string is greater than or equal to 2.

The length of each string is guaranteed to be at least 1.
Input Format
The first line of the input contains an integer 'T' denoting the number of test cases.

The first and the only line of each test case contains a string 'S'.
Output Format:
For each test case, the only line of output of each test case should contain an integer representing the minimum number of lamps to be installed to illuminate the whole string.

The output of each test case will be printed in a separate line.
You do not need to print anything. It has already been taken care of. Just implement the given function.
 1 <= 'T' <= 100
 1 <= |'S'| <= 5 * 10 ^ 4

Where 'T' is the number of test cases, and |'S'| denotes the length of the string.

Time limit: 1 sec.
Approach 1
  • The first thing to note is that for every three continuous dots, we will require one lamp. So if we have 'K' continuous dots, we will need exactly 'K'/3 lamps if 'K' is a multiple of 3. When 'K' is not a multiple of 3, we will require ceil('K' / 3) lamps because if we take the floor('K' / 3) there will be 1 or 2 extra spaces that will not be covered, for that we will require one extra lamp. Hence in total, we need ceil('K' / 3) lamps.
  • Firstly we need to preprocess the string as follows:
  • If you encounter an asterisk at index 'I', then mark its neighboring cells, 'I'.e. 'I'-1 and 'I' + 1 also by an asterisk, provided the adjacent cells exist. This is done because there is no need to install lamps on these cells.
  • Now the only thing left is to count the number of empty dots and apply the formula given in the first point.
  • After preprocessing, let 'ANS' = 0 and count = 0. Start traversing the string from ‘I’ = 0 to ‘N’ - 1 and do the following:
  • If S[i] = ‘*’, then 'ANS' = 'ANS' + ceil('COUNT'/ 3) and 'COUNT' = 0. After finding a star, the number of dots in the current segment will become zero.
  • Else if 'S'['I'] = ‘.’, then 'COUNT' = 'COUNT' + 1.
Try Problem