public boolean isValid(String s) {

    // Map<Character, Integer> map = new HashMap<Character, Integer>();
    // better to use a stack

    Stack<Character> stack = new Stack<Character>();


    for (int i = 0 ; i < s.length() ; i++) {
      char ch = s.charAt(i);
      if (ch == '(' || ch == '[' || ch == '{') {
        stack.push(ch);
      } else {

        // corner case
        if (stack.isEmpty()) {
          return false;
        }

        char leftCh;
        if (ch == ')') {
          leftCh = '(';
        } else if (ch == ']') {
          leftCh = '[';
        } else {
          leftCh = '{';
        }

        char leftPop = stack.pop();
        if (leftCh != leftPop) {
          return false;
        }
      }
    }

    if (!stack.isEmpty()) {
      return false;
    }

    return true;
  }