leetcode RemoveInvalidParentheses

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class RemoveInvalidParentheses {
  /**
   * Remove the minimum number of invalid parentheses in order to make the input string valid.
   * Return all possible results.
   *
   * Note: The input string may contain letters other than the parentheses ( and ).
   *
   * Example 1:
   *
   * Input: "()())()"
   * Output: ["()()()", "(())()"]
   * Example 2:
   *
   * Input: "(a)())()"
   * Output: ["(a)()()", "(a())()"]
   * Example 3:
   *
   * Input: ")("
   * Output: [""]
   */
  public static List<String> removeInvalidParentheses(String s) {
    HashSet<String> visited = new HashSet<>();
    Queue<String> q = new LinkedList<>();
    List<String> res = new LinkedList<>();
    boolean found = false;
    q.offer(s);

    while(!q.isEmpty()){
      s = q.poll();

      if (isValid(s)){
        found = true;
        res.add(s);
      }

      if (found) continue;

      for (int i=0; i<s.length(); i++){
        if (s.charAt(i) == '(' || s.charAt(i) == ')') {
          String t = s.substring(0, i) + s.substring(i+1);
          if (!visited.contains(t)){
            q.offer(t);
            visited.add(t);
          }
        }
      }
    }
    return res;

  }
  public static void main(String[] args) {
    String s = "(())())";
    for (String ss: removeInvalidParentheses(s)){
      System.out.println(ss);
    }
  }
  public static boolean isValid(String s){
    int count = 0;
    for (int i=0; i<s.length(); i++) {
      if (s.charAt(i) == '(') count ++;
      if (s.charAt(i) == ')') {
        if (--count < 0)
          return false;
      }
    }
    return count == 0;
  }
}