Unbalanced String Puzzle

Here is a fun puzzle that I was recently challenged with. We need to determine if a string is balanced if there is a matching opening and closing parenthesis, bracket, or brace. The string must have a matching parenthesis, bracket, or brace, and the matching object must also be in the correct order.

Let’s look at a few examples.

The following three would be considered balanced as they have the objects in the correct order.

( ( { [] } ) )
( ) [ ]
( { } )

The following three would not match as the objects are not in the correct order
( { ) }
( { ) } } } ( )
} { ( ) ] [

Can you figure out the trick to determine if the string is balanced?

Here is some quick test data; just hit the copy button in the upper right of the box.

Spoiler alert! The answer is posted below the following test data DDL statements.

DROP TABLE IF EXISTS ##Match;
GO

CREATE TABLE ##Match
(
RowNumber INT IDENTITY(1,1) PRIMARY KEY,
ExpectedOutcome VARCHAR(50),
MatchString VARCHAR(50),
UpdateString VARCHAR(50)
);
GO

INSERT INTO ##Match (ExpectedOutcome, MatchString) VALUES
('Balanced','( )'),
('Balanced','[]'),
('Balanced','{}'),
('Balanced','( ( { [] } ) )'),
('Balanced','( ) [ ]'),
('Balanced','( { } )'),
('Unbalanced','( { ) }'),
('Unbalanced','( { ) }}}()'),
('Unbalanced','}{()][');
GO

Here is the answer to the puzzle. I’ve also included the table population statements as well; there’s no need to copy both code boxes. The code is pretty simple, and I’ve added comments if any clarification is needed.

DROP TABLE IF EXISTS ##Match;
GO

CREATE TABLE ##Match
(
RowNumber INT IDENTITY(1,1) PRIMARY KEY,
ExpectedOutcome VARCHAR(50),
MatchString VARCHAR(50),
UpdateString VARCHAR(50)
);
GO

INSERT INTO ##Match (ExpectedOutcome, MatchString) VALUES
('Balanced','( )'),
('Balanced','[]'),
('Balanced','{}'),
('Balanced','( ( { [] } ) )'),
('Balanced','( ) [ ]'),
('Balanced','( { } )'),
('Unbalanced','( { ) }'),
('Unbalanced','( { ) }}}()'),
('Unbalanced','}{()][');
GO

--Remove any spaces
--Populates the column UpdateString that we will manipulate with the below UPDATE statements
UPDATE ##Match
SET MatchString = REPLACE(MatchString,' ',''),
    UpdateString = REPLACE(MatchString,' ','');

--Set a Loop Counter
DECLARE @vLoop INTEGER = 1;
WHILE @vLoop <> 0

    --Update the UpdateString column to remove any matching objects
    BEGIN
    ------------------
    UPDATE  ##Match
    SET UpdateString = REPLACE(UpdateString,'()','');
    ------------------
    UPDATE  ##Match
    SET UpdateString = REPLACE(UpdateString,'[]','');
    -------------------
    UPDATE  ##Match
    SET UpdateString = REPLACE(UpdateString,'{}','');
    -------------------

    --Determine if there are any more matching objects to update
    WITH cte_Charindex AS
    (
    SELECT CHARINDEX('()',UpdateString) AS LoopDetermine FROM ##Match
    UNION
    SELECT CHARINDEX('[]',UpdateString) AS LoopDetermine FROM ##Match
    UNION
    SELECT CHARINDEX('{}',UpdateString) AS LoopDetermine FROM ##Match
    )
    SELECT @vLoop = MAX(LoopDetermine) FROM cte_Charindex;
    -------------------

    END;

--If the UpdateString column is empty, then it is a balanced string 
SELECT  *, CASE WHEN UpdateString = '' THEN 'Balanced' ELSE 'Unbalanced' END AS FinalResult 
FROM    ##Match;

Note that this solution requires an iterative-based solution rather than a set-based solution. Although set-based solutions are generally preferred, this is a good example of when to use an iterative-based solution to arrive at your answer.

Happy coding!