对了,我的网名是 (iwi)。 我确实以前参加过程序设计比赛。 而且,和许多朋友度过了快乐的时光。
确实,我感觉我的同伴们全都是美少女。 编程竞赛的世界,仿佛是我的后宫。 G○○gle 一定是夺走了我的后宫,毫无疑问。 为了找到昔日同伴的线索,我果然还是必须参加编程竞赛。
决定报名参加 G○○gle Code Jam。 这次的 ID,也尝试考虑使用圆括号以外的括号吧。
問題
当给定由 'i'、'w'、'('、')'、'{'、'}'、'['、']' 构成的字符串时, 想从中取出子序列,制作出线对称的字符串。 请编写程序计算最多可以制作多少字符的字符串。
给定的字符串会 至少包含一次 "iwi",而其他部分不包含 'i' 和 'w'。 更形式地说,给定的字符串是 s “iwi” t (s 与 “iwi” 以及 t 连接而成的形式表示 s 和 按字典顺序比较 t 由 '(', ')', '{', '}', '[', ']' 组成的字符串。 s 呀 请注意,它可能是 t 也可能是 0 个字符。
所构造的字符串,是从给定的字符串中抽取子序列来构造的。 子序列是指从原始字符串中取出若干字符,然后按它们在原字符串中出现的顺序连接而成。 取出的字符不必在原字符串中连续。
此外,构造的字符串也应像给定字符串一样,包含一次 “iwi” 字符串,并且其他部分不包含 'i' 和 'w'。
这里使用的水平对称的定义如下。
- 以下字符串水平对称。
- 空文字列
- “我”
- “w” 当
- 文字列 x 水平对称时,后面的字符串也水平对称。
- “我” x “我”
- “w” 当 x “w” 当
- "(" x ")"
- ")" x "("
- "{" x "}"
- "}" x "{"
- "[" x "]"
- "]" x "["
- 只有以上项目是左右对称的。
入力
输入由 'i', 'w', '(', ')', '{', '}', '[', ']' 组成,并满足上述条件。
出力
输出可以满足上述条件所能构成的字符串的最大长度。
制約
- 输入字符串的长度不超过15。
入出力例
入出力例 1
入力例 1:
[[[iwi[[[
输入示例 1 的输出示例:
3
只能构造出 "iwi" 这个字符串。
入出力例 2
入力例 2:
[{)iwi(]}
输入示例 2 的输出示例:
7
可以构造出 "[)iwi(]" 或 "{)iwi(}" 等7个字符的字符串。