Remove Invalid Parentheses | Java program to remove invalid parenthesis ; method checks if character is parenthesis ( openor closed ) ; method returns true if string contains valid parenthesis ; method to remove invalid parenthesis ; visit set to ignore already visited string ; queue to maintain BFS ; pushing given string as starting node into queue ; If answer is found , make level true so that valid string of only that level are processed . ; Removing parenthesis from str and pushing into queue , if not visited already ; Driver Code
import java . util . * ; class GFG { static boolean isParenthesis ( char c ) { return ( ( c == ' ( ' ) || ( c == ' ) ' ) ) ; } static boolean isValidString ( String str ) { int cnt = 0 ; for ( int i = 0 ; i < str . length ( ) ; i ++ ) { if ( str . charAt ( i ) == ' ( ' ) cnt ++ ; else if ( str . charAt ( i ) == ' ) ' ) cnt -- ; if ( cnt < 0 ) return false ; } return ( cnt == 0 ) ; } static void removeInvalidParenthesis ( String str ) { if ( str . isEmpty ( ) ) return ; HashSet < String > visit = new HashSet < String > ( ) ; Queue < String > q = new LinkedList < > ( ) ; String temp ; boolean level = false ; q . add ( str ) ; visit . add ( str ) ; while ( ! q . isEmpty ( ) ) { str = q . peek ( ) ; q . remove ( ) ; if ( isValidString ( str ) ) { System . out . println ( str ) ; level = true ; } if ( level ) continue ; for ( int i = 0 ; i < str . length ( ) ; i ++ ) { if ( ! isParenthesis ( str . charAt ( i ) ) ) continue ; temp = str . substring ( 0 , i ) + str . substring ( i + 1 ) ; if ( ! visit . contains ( temp ) ) { q . add ( temp ) ; visit . add ( temp ) ; } } } } public static void main ( String [ ] args ) { String expression = " ( ) ( ) ) ( ) " ; removeInvalidParenthesis ( expression ) ; expression = " ( ) v ) " ; removeInvalidParenthesis ( expression ) ; } }