A string ‘STR’ containing either ‘{’ or ‘}’. ‘STR’ is called valid if all the brackets are balanced. Formally for each opening bracket, there must be a closing bracket right to it.

For Example:
“{}{}”, “{{}}”, “{{}{}}” are valid strings while “}{}”, “{}}{{}”, “{{}}}{“ are not valid strings.
Ninja wants to make ‘STR’ valid by performing some operations on it. In one operation, he can convert ‘{’ into ‘}’ or vice versa, and the cost of one such operation is 1.
Code is

int solve(string str, stack<char>& s, int i) {
    if (i >= str.length()) {
        return 0;
    }
    if (str[i] == '{') {
        s.push('{');// 
    } else {
        if (!s.empty() && s.top() == '{') {
            s.pop();
        } else {
            s.push('}');
        }
    }
    return solve(str, s, i + 1);
}

int valid(stack<char>& s) {
    int count = 0;
    while (!s.empty()) {
        char x = s.top();
        s.pop();
        if (!s.empty()) {
            char y = s.top();
            s.pop();
            if (x == y) {
                count++;
            } else {
                count += 2;
            }
        }
    }
    return count;
}

int findMinimumCost(string str) {
    if ((str.length() % 2) != 0) {
        return -1;
    }
    stack<char> s;
    solve(str, s, 0);
    if (s.empty()) {
        return 0;
    } else {
        return valid(s);
    }
}

I have tried to check if the string is valid by Solve function and if it is not I called valid function. I have created a count variable which stores the cost ,means how many changes I have to make to make the string valid.
Solve function checks if the string input is open bracket then it is pushed into the stack and if it closed bracket and top of the stack is open bracket then pop is called.
And after reaching the end of the string, it will return the count.
If the stack is not empty, it means brackets are not balanced so valid function is called.
In valid function, I store the top element of the stack (in X variable) and pop it and check if the stack is not empty then store the top element(in Y variable) and pop it . After then I compared if (X==Y) then count is incremented by 1 if the x=’}’ and y='{‘ the count is incremented by 2.
After the stack is empty I returned count.

After submitting the code ,it failed in One test case(bigger one ) and it says the solution is optimal one.