Seats

• Time : $O(n)$
• Space : $O(n)$

long long mod = 10000003;
int Solution::seats(string A) {
    int n = A.size();
    if(n == 1) return 0;
    vector<long long> dp(n), dpp(n);
    for(long long i = 0, now = 0; i < n; i++) {
        if(i) dp[i] = dp[i - 1];
        if(A[i] == 'x') now += 1;
        else dp[i] += now;
    }
    for(long long i = n - 1, now = 0; i >= 0; i--) {
        if(i + 1 != n) dpp[i] = dpp[i + 1];
        if(A[i] == 'x') now += 1;
        else dpp[i] += now;
    }
    long long res = LLONG_MAX;
    for(int i = 1; i < n; i++) res = min(res, dp[i-1] + dpp[i]);
    return res % mod;
}