p535.ans1
======================
3

=================
p535.ans2
======================
3

=================
p535.ans3
======================
4

=================
p535.ans4
======================
-1

=================
p535.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

const int INF = 1e9;

string s;
string t;
int n;
vector<vector<int>> dp;
vector<int> split_pts;

void read() { cin >> s; }

int f(int l, int r) {
    if(l > r) {
        return 0;
    }

    int& res = dp[l][r];
    if(res != -1) {
        return res;
    }

    res = INF;

    if(t[l] == '*' && t[r] == '*') {
        res = min(res, f(l + 1, r));
        res = min(res, f(l, r - 1));
    } else if(t[l] == '*') {
        if(isupper(t[r])) {
            res = min(res, f(l, r - 1) + 1);
        }
        res = min(res, f(l + 1, r));
    } else if(t[r] == '*') {
        if(islower(t[l])) {
            res = min(res, f(l + 1, r) + 1);
        }
        res = min(res, f(l, r - 1));
    } else if(islower(t[l]) && isupper(t[r]) && t[l] == (char)tolower(t[r])) {
        res = min(res, f(l + 1, r - 1));
    }

    for(int i: split_pts) {
        int lo = (t[i] == '*') ? l + 1 : l;
        if(i >= lo && i < r) {
            int rl = (t[i] == '*') ? i : i + 1;
            res = min(res, f(l, i) + f(rl, r));
        }
    }

    return res;
}

void solve() {
    // First sweep greedily cancels adjacent matched pairs: lowercase 'x'
    // followed by uppercase 'X' is a real push-pop pair, so pop them off a
    // stack. A lowercase top against a non-matching uppercase is an outright
    // contradiction => -1. After this reduction, t consists of stars and
    // chains shaped like upper-upper-...upper-lower-lower-...lower (any pops
    // that survive must precede any pushes that survive, otherwise they'd
    // have cancelled). Only stars can balance what remains.
    //
    // f(l, r) = min number of extra letters the stars in t[l..r] must produce
    // so that t[l..r] becomes a fully balanced bracket sequence (lowercase =
    // open, uppercase = close). Endpoint cases handle stars at the borders
    // absorbing one neighbor as their matching bracket, and a matched pair at
    // the borders. We also try every "natural split" point: a star (which can
    // split into two stars covering both halves) or a position between an
    // uppercase and a lowercase (the only place an outer balanced sequence
    // can be cut in two without crossing an active matching pair).

    string reduced;
    int kept = 0;
    for(char c: s) {
        if(c != '*') {
            kept++;
        }

        if(c == '*' || islower(c)) {
            reduced.push_back(c);
        } else if(reduced.empty() || reduced.back() == '*' || isupper(reduced.back())) {
            reduced.push_back(c);
        } else if(reduced.back() == (char)tolower(c)) {
            reduced.pop_back();
        } else {
            cout << -1 << '\n';
            return;
        }
    }

    t = reduced;
    n = (int)t.size();

    split_pts.clear();
    for(int i = 0; i < n; i++) {
        if(t[i] == '*' || (i + 1 < n && isupper(t[i]) && islower(t[i + 1]))) {
            split_pts.push_back(i);
        }
    }

    dp.assign(n, vector<int>(n, -1));

    int extra = (n == 0) ? 0 : f(0, n - 1);
    if(extra >= INF) {
        cout << -1 << '\n';
    } else {
        cout << (extra + kept) / 2 << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}

=================
p535.in1
======================
ab*bB

=================
p535.in2
======================
afFaAA

=================
p535.in3
======================
**bbB*Da*

=================
p535.in4
======================
a**b

=================
statement.txt
======================
535. Dirty Dishes
Time limit per test: 1 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

They say there are three things that one cannot have enough of looking at: they are the fire burning, the water flowing and others working. Jack and Jill have been married for several years but Jack never gets tired of watching Jill cleaning the kitchen in her swift and neat way!

As Jill is cleaning the kitchen, she piles up the dirty dishes by the sink. Each newly found dirty dish is put on the top of the pile and when Jill wants to wash the dishes, she takes a dish from the top of the pile.

Jack has been watching his wife attentively and each time she added a new dirty c-colored dish to the pile, Jack made a note in his notebook that a c-colored dish had been added to the pile. Similarly, when Jill took a c-colored dish from the top of the pile, Jack noted that a c-colored dish had been taken from the pile. From time to time Jack would leave to get more popcorn and then he would probably miss some of Jill's actions. In this case he wrote an asterisk "*" in his notebook.

Next day, as Jack was scanning through the notes, he got interested: what is the least number of dirty dishes that could be on the kitchen before the cleaning? Note that Jill doesn't arrange the dishes in more than one pile. Jill only puts the dishes to the top of the pile and only takes them from the top of the pile. Before the cleaning and after it the pile is empty.

Input
The only input line contains the notes from Jack's notebook. Using Latin alphabet, he wrote a lowercase letter if Jill added a dish of the corresponding color to the pile. Also, Jack wrote an uppercase letter if Jill took a dish of the corresponding color from the pile. For example, the string "afFaAA" represents the following actions:
Jill adds an a-colored dish to the pile,
Jill adds an f-colored dish to the pile,
Jill takes an f-colored dish from the pile,
Jill adds an a-colored dish to the pile,
Jill takes an a-colored dish from the pile,
Jill takes an a-colored dish from the pile.


An "*" represents the periods of time when Jack went to get more popcorn and could have missed one or more Jill's actions. It is guaranteed that Jack went to get more popcorn no more than five times. So the number of characters "*" doesn't exceed 5.

The given string consists of lowercase and uppercase Latin letters and asterisks "*". It is not empty and contains no more than 2500 characters. The input contains at least one letter.

Output
On the first line of the input file print the single number — the least possible number of dirty dishes on the kitchen before the cleaning. Print -1 if Jack's notes surely have a mistake and there's no solution.

Example(s)
sample input
sample output
ab*bB
3

sample input
sample output
afFaAA
3

sample input
sample output
**bbB*Da*
4

sample input
sample output
a**b
-1



Note
An example of a sequence of actions for the first sample is abBAbB.

In the second sample Jack never left the room.

In the third sample he left the room four times, two of them one after another. An example of Jill's action succession is like that: "bbBdDaAB".

The fourth sample illustrates no solution.


=================
