Count the number of strings that with k fixes can be turned to a valid parentheses expression

Question

Given a number n, we can count all the valid parentheses expressions of lengths 2n and their number is equal to C(n) - Catalan number n. How can I count the number of strings that are almost k valid as function of k and n? for example the string "((()" is almost 1 valid since we can change 1 parenthesis and obtain "(())" or "()()" and the string "((((" is almost 2 valid since we need to change at least 2 parenthesis and obtain "(())" or "()()". k denotes the number of minimal changes that should be done to get a valid string.