Виправити розстановку дужок

Дано рядок, що складається з дужок; ваше завдання — отримати правильний рядок, змінивши мінімальну кількість символів. Видаляти або вставляти символи не дозволяється.

Існують три типи дужок: круглі $()$, квадратні $[]$ та фігурні $\{\}$. Кожна пара складається з відкривальної дужки ($($, $[$, $\{$) і закривальної дужки ($)$, $]$, $\}$).

Правильний рядок визначається наступними правилами:

• Порожній рядок є правильним.

• Якщо $s$ — правильний рядок, то $(s)$, $[s]$ та $\{s\}$ також правильні.

• Якщо $s$ та $t$ — правильні рядки, то їх конкатенація $st$ також є правильною.

Наприклад, рядки «([{}])», «» та «(){}[]» правильні, тоді як «([}])», «([)]» та «{» — ні. Для заданого рядка знайдіть мінімальну кількість змін, необхідних для отримання правильного рядка.