I think there is a more space efficient solution to problem 22.13.
There is no need for a stack, two passes are enough, one from left and one from right.
Made a sketch about the idea: Problem 22.13 solution idea
Left pass is shown with orange, right with red.
Whenever the parentheses balance becomes invalid, the balance and rolling length is thrown away.
If the balance becomes zero in a valid way, a valid substring is detected. The problematic part
is only the tail, which is handled by the right pass symmetrically.
public static int validParanthesizationMaxLen(String str){
if (str == null || str.length() == 0) return 0;
return Math.max(leftMax(str), rightMax(str));
}
static int leftMax(String str){
return max(str, '(', 0, str.length()-1, 1);
}
static int rightMax(String str){
return max(str, ')', str.length()-1, 0, -1);
}
static int max(String str, char par, int start, int end, int dir){
int max = 0;
int balance = 0;
int len = 0;
for(int i = dir*start; i <= dir*end; ++i){
char c = str.charAt(dir*i);
if (c == par){
++balance;
++len;
} else if (balance > 1){
--balance;
++len;
} else if (balance < 1){
balance = 0;
len = 0;
} else {
--balance;
++len;
max = Math.max(max, len);
}
}
return max;
}