Daily bit(e) of C++ | Longest string with valid parenthesis
Daily bit(e) of C++ #329, Common interview problem: Longest string with valid parenthesis.
Today, we will look at a common C++ interview problem: Longest string with valid parenthesis.
Given a string that contains parentheses ‘(‘,’)’ intermixed with other characters, return the longest string (formed by removing some characters) that contains only valid parentheses. If there are multiple such strings, return any.
For example, for the string “()))(a((b)()c(()(“, one possible result is “()a(b)()c()”, however, “()a((b)()c)” is also valid.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/Y7MMGWGhc.
Solution
If we do a left-to-right pass, we can filter out excessive ‘)’ parenthesis by ensuring enough preceding left parenthesis. And we can apply the same logic in the inverse direction.
So, one solution would be to process the string twice using the above logic. However, we can do slightly better. Once we scan the string, we know how many parentheses are remaining and, therefore, how many we must remove.
The second observation is that if we are processing left-to-right and have excessive ‘)’ parentheses, it is always correct to remove the earliest instances. And again, the same logic applies to the left parenthesis when processing in the opposite direction.
Putting this all together, we can do all processing in place. First, we process right-to-left, removing excessive ‘(‘ parenthesis, then left-to-right, moving the string back into position (starting at index zero), removing the leading excessive ‘)’ parenthesis.
std::string longest_valid_string(std::string s) {
auto dst = s.rbegin();
int64_t left = 0;
int64_t right = 0;
// Right-to-left, remove excessive '('.
for (auto it = s.rbegin(); it != s.rend(); ++it) {
if (*it == ')') {
++right;
} else if (*it == '(') {
// This instance is excessive, do not copy.
if (left == right) continue;
++left;
}
// Since we are working with characters,
// the std::move is superfluous.
*dst = std::move(*it);
++dst;
}
// Left-to-right, remove excessive ')'.
auto dst_fwd = s.begin();
int64_t to_remove = right-left;
// We have moved the non-removed characters to the right
// so the string now starts at dst.base().
for (auto it = dst.base(); it != s.end(); ++it) {
if (*it == ')' && to_remove > 0) {
// This instance is excessive, do not copy.
--to_remove;
continue;
}
// Since we are working with characters,
// the std::move is superfluous.
*dst_fwd = std::move(*it);
++dst_fwd;
}
// Remove the now invalid tail of the string.
s.erase(dst_fwd, s.end());
return s;
}