D - Scope Editorial by spheniscine


Let’s maintain three data structures:

  • \(box\), a stack (vector in C++, ArrayList in Java/Kotlin) of the items in the box
  • \(in\), an array of \(26\) booleans, indicating whether each letter is in the box
  • \(brk\), another stack. The last/top element indicates the number of elements in \(box\) at the time of the last unmatched (.

So we can process \(S\) character by character:

  • if \(S_i\) is an English letter, check \(in\); if that character’s already in the box, print No and terminate, otherwise add it to \(box\) and update \(in\).
  • if \(S_i\) is (, append the current length of \(box\) to \(brk\)
  • if \(S_i\) is ), remove the last element of \(brk\). We wish to “undo” the additions to \(box\) until \(box\) is that length again. Remove those elements from \(box\) and update \(in\).

As stacks are amortized \(O(1)\) for appending an element and removing the last element, the total time is \(O(N)\).

posted:
last update: