Number of balanced strings

Revision en1, by nik1996, 2018-07-11 11:08:38

Given 2 strings of parenthesis. You need to make another string using these 2 strings such that in the resulting string, all the parenthesis are balanced. Ordering of parenthesis must not change, e.g. if u take 2 characters/parenthesis from 1st string, then order of these parenthesis must not change in resulting string. You need to tell number of balanced strings you can make. Examples: )) (( ans:2, you can make ()() and (()) Expected Time Complexity: O(n*m) where n and m are length of strings.

Could anyone tell how this problem can be solved in O(n*m) time?


  Rev. Lang. By When Δ Comment
en2 English nik1996 2018-07-11 11:14:21 85
en1 English nik1996 2018-07-11 11:08:38 597 Initial revision (published)