Count the Number of Special Characters II
Real-world version: Sections Drafted Before Being ApprovedThe statement here is our own: the same inputs, outputs and technique.
A document has up to 26 sections, each tagged by one letter of the alphabet. An audit trail arrives as the string log, one character per touch, read left to right in the order the touches happened:
- a lowercase letter is a draft touch on the section with that tag;
- the same letter uppercase is an approval touch on that same section.
A section is settled when the trail shows at least one draft touch on it, at least one approval touch on it, and no draft touch on it after its earliest approval touch.
Return how many sections are settled.
Examples
Example 1
- Input
- log = "ppPqrQR"
- Output
- 3
Section p is drafted at positions 0 and 1 and approved at position 2. Section q is drafted at position 3 and approved at position 5, and section r is drafted at position 4 and approved at position 6. All three have every draft touch ahead of their first approval.
Example 2
- Input
- log = "mMm"
- Output
- 0
Section m is drafted at position 0, approved at position 1, then drafted again at position 2. That final draft touch comes after the approval, so the section is not settled.
Example 3
- Input
- log = "ffFgGf"
- Output
- 1
Section g is drafted at position 3 and approved at position 4, so it is settled. Section f is drafted at positions 0, 1 and 5 and approved at position 2, and the touch at position 5 falls after that approval.
Constraints
- 1 <= log.length <= 2 * 10^5
- log consists only of lowercase and uppercase English letters.
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def count_promoted_letters(log: str) -> int:public int countPromotedLetters(String log)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 14 test cases: 14 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's