Why this Code ,which finds Minimum Cost To Make String Valid not works properly for larger test cases?

Question

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.

Answer 1

I don't think you need a stack or any other additional data structure for this algorithm. Notice that whenever you find a closing bracket } it can always match any previous open bracket {, so it should be enough to simply keep track of number of open brackets.

Then when you see } and the count of { is 0, it means you need to perform the change operation.

Then after iterating over all characters of the string, if you are left with non-zero open brackets count, it means you need to change half of them (assuming the number is even, but I leave it to you to take care of some corner cases).

This should be enough:

int foo(std::string input) {
    int openCount = 0;
    int cost = 0;
    for (auto c : input) {
        if (c == '{') {
            openCount++;
        }
        if (c == '}') {
            if (openCount > 0) {
                openCount--;
            }
            else {
                openCount++;
                cost++;
            }
        }
    }
    if (openCount > 0) {
        cost += openCount/2;
    }
    return cost;
}

Tested with:

int main()
{
    std::cout << foo("{{{}}}") << std::endl; // 0
    std::cout << foo("{{{}}{{{") << std::endl; // 2
    std::cout << foo("}}}}") << std::endl; // 2
    std::cout << foo("{{{{") << std::endl; // 2

}