Coding: a DP problem on Balanced Parenthesis

Problem link — InterleavingParenthesisDiv2

This is a classic dynamic programming (dp) problem. Before discussing dp, let’s try to derive some additional properties of balanced parenthesis along with basic properties.

The length of a balanced parenthesis sequence is even. From one basic property we know: If “X” is a correct sequence, then “(X)” is a correct sequence. We see that, each time length of ‘X’ is incremented by 2 [one left ‘(‘ and one right ‘)’ ] and sequence starts from length 0. So parity remains even. Even…



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store