Minimum Cost to Make String Valid Problem in Java

Given a string containing only characters '(' and ')', the task is to determine the minimum cost to make the string valid. The cost is incurred for each replacement operation where you can replace a character with its counterpart. The goal is to make every open parenthesis '(' have a corresponding closing parenthesis ')'.

Example 1:

Input: "())"

Output: Minimum Cost to Make String Valid: 1

Explanation:

The input string "())" is not valid because the closing parenthesis at index 2 has no matching open parenthesis. We replace the ')' at index 2 with '(' to make the string valid: "()". The cost incurred is 1.

Example 2:

Input: " ((())"

Output: Minimum Cost to Make String Valid: 1

Explanation:

The input string "((())" is not valid because the closing parenthesis at index 3 has no matching open parenthesis. We replace the ')' at index 3 with '(' to make the string valid: "(()())". The cost incurred is 1.

Example 3:

Input: "()"

Output: Minimum Cost to Make String Valid: 0

Explanation:

The input string "()" is already valid, so no replacements are needed. The cost incurred is 0.

Approach:

Step 1: Traverse the string from left to right.

Step 2: Use a stack to keep track of the indices of open parentheses '('.

Step 3: When encountering a closing parenthesis ')', check for a matching open parenthesis in the stack.

• If a match is found, pop the open parenthesis from the stack.
  • If no match is found, replace the closing parenthesis with '*' and incur a cost.

Step 4: After processing the entire string, replace any remaining unmatched open parentheses with '*' and incur the corresponding cost.

Implementation:

Filename: MinimumCostToMakeStringValid.java

import java.util.Stack;

public class MinimumCostToMakeStringValid {

    public static int minCostToMakeValid(String s) {

        int cost = 0;

        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {

            char c = s.charAt(i);

            if (c == '(') {

                stack.push(i);

            } else if (c == ')') {

                if (!stack.isEmpty()) {

                    stack.pop();

                } else {

                  // No matching open parenthesis found, replace ')' with '*' and incur a cost.

                    s = s.substring(0, i) + '*' + s.substring(i + 1);

                    cost++;

                }

            }

        }

        // Replace any remaining unmatched open parentheses with '*' and incur the corresponding cost.

        while (!stack.isEmpty()) {

            s = s.substring(0, stack.pop()) + '*' + s.substring(stack.peek() + 1);

            cost++;

        }

        return cost;

    }

    public static void main(String[] args) {

        String input = "()))";

        int result = minCostToMakeValid(input);

        System.out.println("Minimum Cost to Make String Valid: " + result);

    }

}

Output:

Minimum Cost to Make String Valid: 2

Complexity analysis:

Time Complexity: The time complexity of this code is O(N), where N is the length of the input string s. The loop iterates over the string runs in O(N) time. Stack operations (push, pop) within the loop also take constant time.

Space Complexity: The space complexity is O(N), where N is the length of the input string s. The main contributor to the space complexity is the stack used to keep track of the indices of open parentheses.