Indices of Enclosing Parentheses | Dataford Interview Questions

The Outreach sequence editor supports parenthesized template expressions. Given a balanced string and the index of a non-parenthesis character, return the indices of the innermost pair of parentheses that strictly encloses that character.

If the character is not enclosed by any parentheses, return [-1, -1].

Formal Specification

Implement find_enclosing_parentheses(s, target_index):

s is a string containing lowercase letters, spaces, and parentheses.
target_index is a valid index of a non-parenthesis character in s.
The parentheses in s are balanced and properly nested.
Return [open_index, close_index] for the innermost enclosing pair, where open_index < target_index < close_index.
Return [-1, -1] when no pair encloses the target.

Constraints

1 <= len(s) <= 10^5
0 <= target_index < len(s)
s[target_index] is not '(' or ')'
s contains balanced, properly nested parentheses

Function Signature

def find_enclosing_parentheses(s, target_index):

Your question is Indices of Enclosing Parentheses. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem