Make Valid Parentheses Sequence: Minimum Insertions and Deletions

ID: 34130

Type: Default

1000ms

256MiB

Given a string (s) consisting only of the characters '(', ')', '{', '}', '[' and ']', determine the minimum number of insertion or deletion operations required to transform (s) into a valid parentheses sequence. A sequence is considered valid if every opening bracket has a matching closing bracket in the correct order.

For example, if (s = ([)]), the minimum number of operations required is 2.

inputFormat

A single line containing the string (s) composed solely of the characters '(', ')', '{', '}', '[' and ']'.

outputFormat

Output a single integer on stdout representing the minimum number of insertions or deletions required to make the input string a valid parentheses sequence.## sample

([)]

#K74132. Make Valid Parentheses Sequence: Minimum Insertions and Deletions

Make Valid Parentheses Sequence: Minimum Insertions and Deletions