Remove Invalid Parenthesis

//Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.



package gfg;

import java.util.ArrayList;
import java.util.List;

public class RemoveInvalidParenthesis {

	public static List<String> removeInvalidParentheses(String s) {
		ArrayList<String> result = new ArrayList<String>();
		if (s == null)
			return result;

		dfs(s, "", 0, 0, result);
		if (result.size() == 0) {
			result.add("");
		}

		return result;
	}

	public static void dfs(String left, String right, int countLeft, int maxLeft, ArrayList<String> result) {
		int max = 0;
		if (left.length() == 0) {
			if (countLeft == 0 && right.length() != 0) {
				if (maxLeft > max) {
					max = maxLeft;
				}

				if (maxLeft == max && !result.contains(right)) {
					result.add(right);
				}
			}

			return;
		}

		if (left.charAt(0) == '(') {
			dfs(left.substring(1), right + "(", countLeft + 1, maxLeft + 1, result);// keep (
			dfs(left.substring(1), right, countLeft, maxLeft, result);// drop (
		} else if (left.charAt(0) == ')') {
			if (countLeft > 0) {
				dfs(left.substring(1), right + ")", countLeft - 1, maxLeft, result);
			}

			dfs(left.substring(1), right, countLeft, maxLeft, result);

		} else {
			dfs(left.substring(1), right + String.valueOf(left.charAt(0)), countLeft, maxLeft, result);
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		String str = "())()";
		List<String> ans = removeInvalidParentheses(str);
		System.out.println(ans);
	}

}