# 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:

`1`

# Explanation 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.

# 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)

# Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.

--

--

--

## More from Placewit

Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.

## Placewit

Upskilling students for tech placements!