Check balanced parentheses in a string

Given a string with parentheses (round brackets) and letters, validate the parentheses:
1. An opening parentheses '(' should have a closing matching parentheses ')'.
2. Closing matching parentheses should not come before an opening parentheses.
Note: Assume that the string has alphabets and numbers and round brackets only.

For example:
((BCD)AE) - Valid
)(PH)N(X) - Invalid


Question Asked in

Amazon, Microsoft


Video coming soon!



Subscribe for more updates


Preparing for interviews? IDeserve team is here to help.




Algorithm/Insights

1. Iterate over the string.
2. Create count = 0, increment count if an opening parentheses is seen, decrement count if a closing parentheses is seen.
3. If when a closing parentheses is seen and count is 0, then it means that the current closing parentheses does not have a matching opening parentheses, so return false.
4. When iteration completes, if count is not 0, it means there is an opening parentheses without a matching closing parentheses, so return false.
5. If count is 0, return true.

We will create a separate post for validating an expression having multiple types of parentheses (round brackets (), curly brackets {}, square brackets [] etc)


Hone your coding skills!




AngryNerds Practice platform »

Algorithm Visualization




Code Snippet

			
package com.ideserve.questions.saurabh;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Given a string with parentheses (round brackets) and letters, validate the parentheses.
 *
 * @author Saurabh
 */
public class Parentheses {

	public static boolean isValid(String str) {

		if (str == null || str.length() == 0) {
			return true;
		}

		int count = 0;
		int i = 0;
		while (i < str.length()) {
			char ch = str.charAt(i);
			if (ch == '(') {
				count++;
			} else if (ch == ')') {
				if (count == 0)
					return false;
				else
					count--;
			}
			i++;
		}

		if(count != 0) 
			return false;
		
		return true;
	}
	
	public static void main(String[] args) {
		String str = "((BCD)AE)";
		System.out.println("isValid: " + isValid(str));
		str = ")(PH)N(X)";
		System.out.println("isValid: " + isValid(str));
	}
}
		

Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(1)


Contribution

  • Sincere thanks from IDeserve community to Saurabh Kumar for compiling current post.

    Saurabh Kumar

    Ninja Programmer