Problem

You’re on-call for a fintech platform processing millions of card payments per day. Every payment provider webhook includes a compact “signature pattern” that your edge service must validate before accepting the event (rejecting invalid signatures prevents fraud and reduces chargeback risk).

A signature pattern is a string containing only:

• '(' and ')' — literal parentheses
• '*' — a wildcard that can represent either '(', ')', or the empty string ''

A signature is considered valid if there exists some replacement of every '*' such that the resulting string is a balanced parentheses string.

Task

Implement is_valid_signature(pattern: str) -> bool.

A balanced parentheses string means:

1. Every prefix has #('(') >= #(')').
2. Total counts match at the end.

Examples

Example 1

• Input: pattern = "(*)"
• Output: True
• Explanation: Replace '*' with '' to get "()", which is balanced.

Example 2

• Input: pattern = "(*))"
• Output: True
• Explanation: Replace '*' with '(' to get "(())".

Example 3

• Input: pattern = ")*("
• Output: False
• Explanation: The string starts with ')'. No replacement of '*' can fix the invalid prefix.

Notes

• The interview expectation is not just correct logic, but also professional-grade unit tests: cover edge cases, tricky wildcard interactions, and regressions.
• Your function must run efficiently for long patterns.

Constraints

• 1 <= len(pattern) <= 10^5
• pattern[i] is one of '(', ')', '*'