Solution: Removing Adjacent Pairs

The first attempt paired an opening bracket with a closing bracket without looking at the brackets between them. So let’s only pair brackets when there is nothing between them. That means an opening bracket immediately followed by a closing bracket of the same type, like the () in {[()]}. An adjacent pair like this is always matched correctly, because there is nothing between the two brackets to close in the wrong order.

This suggests an algorithm: find an adjacent matched pair, remove it, and repeat. Removing a pair can make a new pair adjacent, so we keep going. If the string shrinks down to empty, it is valid. If at some point the string is not empty but has no adjacent pair left to remove, it is invalid.

Let’s trace it on {[()]}:

{[()]}   remove ()
{[]}     remove []
{}       remove {}
(empty)  valid

And on ([)]:

([)]     no adjacent matched pair: ([ , [) , )] are not pairs
([)]     stuck, and the string is not empty: invalid

And on (():

(()      remove ()
(        stuck, and the string is not empty: invalid

Let’s check some edge cases. An empty string: nothing to remove, the string is empty, so we return valid, which is correct. A single character: nothing to remove, the string is not empty, so we return invalid, which is correct. The string )(: the characters are adjacent but )( is not a matched pair (the closer comes first), so nothing is removed, the string is not empty, and we return invalid.

When we find an example where our algorithm fails, we have proved it is incorrect. In this case, I cannot find any example where it fails, so it seems correct. To be sure, we would need a proof that the algorithm works for all valid strings. We will not work out that proof in this course.

Proof of correctness for the brute-force solution

If you are curious what that proof might look like, here is an informal version of it:

Take a valid string that is not empty, and find its first closing bracket. Call its index $i$ . Everything at indices $0$ through $i - 1$ is an opening bracket, because $i$ is the first closer in the string.

Now ask which opener the closer at $i$ is paired with. It should be the one right before it at $i - 1$ . Suppose it is not the one right before it, but some earlier opener at index $k$ , with $k < i - 1$ . Then the opener at $i - 1$ sits inside the pair $(k, i)$ , so it has to be closed before index $i$ .

But there is no closing bracket before index $i$ at all, so its partner would have to come after $i$ , which puts it outside the pair.

The arrangement I am describing is similar to the crossing we saw in ([)], which is not a valid string.

So the closer at $i$ is paired with the opener at $i - 1$ (the string is valid, so the closer at $i$ has a partner, and we have ruled out every opener before $i - 1$ ).

So the characters at indices $i - 1$ and $i$ form an adjacent matched pair in the valid string. Removing that pair leaves a string that is still valid, since the removal takes out a complete pair and leaves every other bracket with its partner.

So the same argument applies to what is left, and we can keep applying it until nothing remains. The algorithm never gets stuck on a valid string.

To implement this, we can use the replace method of String: it returns a new string with every occurrence of a target replaced. Replacing a pair with the empty string deletes it. We keep replacing until a full pass removes nothing:

public static boolean isValid(String s) {
  boolean changed = true;
  while (changed) {
    int lengthBefore = s.length();
    s = s.replace("()", "");
    s = s.replace("[]", "");
    s = s.replace("{}", "");
    changed = s.length() < lengthBefore;
  }
  return s.isEmpty();
}

Strings in Java are immutable: replace does not change s, so we assign its result back to s.

Immutable objects

Once a String object is created, it cannot be changed.

You can make immutable objects yourself by declaring a class with final fields and no mutator methods. For example, a Student class with final String name and final int id fields, and only getter methods, would be immutable. Once you create a Student object, you cannot change its name or id.

Immutable objects have some advantages: they are simpler to reason about, they can be safely shared between threads without synchronization, and they can be used as keys in hash tables without worrying about their state changing. We will see immutability again in the chapter on hash tables.

Let’s analyze the complexity of this brute-force solution. Time complexity: Each iteration of the while loop scans the string a constant number of times, which is $O (n)$ work, and each iteration that changes the string removes at least two characters, so there are at most $n /2$ iterations. In the worst case, a deeply nested string like (((( ... )))) has only one adjacent pair per pass, so the loop runs about $n /2$ times, and the total time is $O (n^{2})$ .

Auxiliary space complexity: Each call to replace creates a new string, so the space used at any time is proportional to the length of the string, which is $O (n)$ .