Skip to content

Instantly share code, notes, and snippets.

@brunaaleixo
Created January 4, 2019 18:39
Show Gist options
  • Save brunaaleixo/8c66231ccf090092005c38654b27f987 to your computer and use it in GitHub Desktop.
Save brunaaleixo/8c66231ccf090092005c38654b27f987 to your computer and use it in GitHub Desktop.
int main() {
int n;
cin >> n;
int isValid = 0;
map<int, int> needsLeft;
map<int, int> needsRight;
for (int i = 0; i < n; i++) {
string brackets;
cin >> brackets;
int left, right;
left = right = 0;
int startsWithRight, endsWithLeft;
startsWithRight = brackets[0] == ')';
endsWithLeft = brackets[brackets.size()-1] == '(';
for (auto &c: brackets) {
if (c == '(') {
left++;
} else {
right++;
}
}
// if starts w right and ends with left, paring wont create a valid
// sequence
if (!(startsWithRight && endsWithLeft)) {
int diff = abs(left - right);
if (left > right) {
needsRight[diff]++;
} else if (right > left) {
needsLeft[diff]++;
} else {
isValid++;
}
}
}
int cont = isValid / 2;
map<int, int>::iterator it;
for (it = needsLeft.begin(); it != needsLeft.end(); it++) {
if (needsRight[it->first] > 0) {
cont += min(it->second, needsRight[it->first]);
}
}
cout << cont << endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment