Minimum Number Of Lamps

Easy
0/40
Average time to solve is 10m
profile
Contributed by
14 upvotes
Asked in companies
AdobeAmazonCoinbase

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
 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.
Sample Input 1:
1
……
Sample Output 1:
2
Explanation of Sample Input 1:
For the given string, since no lamps are installed initially if we install one lamp at index 2, it will light up indices 1,2,3 and another lamp at index 5, it will light up index 4, 5, 6. Hence the answer is 2.
Sample Input 2:
3
*.
.*
*.*..
Sample Output 2:
0
0
1
Explanation of Sample Input 2
For the first and second test case, we don’t need to install any lamp, as they will be illuminated by their neighbouring cells.
For the third test case, indices from 1 to 4 will be illuminated. We only need to install one lamp at index 5. Hence the answer is 1.
Hint

Greedy and some Maths.

Approaches (1)
Greedy algorithm
  • 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.
Time Complexity

O(N), where N is the length of the string.

 

Since we are doing a linear search.

Space Complexity

O(1).

 

Since we are not using any extra space.

Code Solution
(100% EXP penalty)
Minimum Number Of Lamps
Full screen
Console