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.
Sample Input:
*.*..Sample Output:
1Explanation for Test Case :
For the given 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.
Approach :
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)
Space Complexity : O(1)
