847E - Packmen - CodeForces Solution

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

int N;
string line;

bool ok(int mid) {
	int p = -1, a = -1;
	int pUsed = -1;
	for (int i = 0; i < N; i++) {
		if (line[i] == '*') {
			if (a == -1) {
				if (p != -1) {
					bool cover;
					if (pUsed > 0) {
						int pToUse = i - p;
						int minUse = min(pUsed, pToUse);
						int maxUse = max(pUsed, pToUse);
						if (2*minUse+maxUse <= mid) cover = true;
						else cover = false;
					} else {
						cover = (i-p <= mid);
					}
					if (!cover) {
						p = -1;
						pUsed = -1;
						a = i;
					}
				} else {
					a = i;
				}
			}
		} else if (line[i] == 'P') {
			if (p == -1) {
				p = i;
				if (a != -1) {
					if (i - a > mid) return false;
					pUsed = (i-a);
					if (mid-pUsed <= 1) {
						p = -1;
						pUsed = -1;
					}
					a = -1;
				} else {
					pUsed = -1;
				}
			} else {
				p = i;
				pUsed = -1;
			}
		}
		//cout << mid << ", " << i << ": " << p << "/" << a << "/" << pUsed << endl;
	}
	if (a > 0) return false;
	return true;
}

int main() {
	cin >> N >> line;
	int lo = 0, hi = N*2;
	while (lo < hi) {
		int mid = lo + (hi-lo)/2;
		if (ok(mid)) {
			hi = mid;
		} else {
			lo = mid+1;
		}
	}
	cout << lo << endl;
}