Remove minimum parentheses to balance string

Given a string s containing lowercase letters and the characters '(' and ')', remove the minimum number of parentheses so that the resulting string is valid (balanced and properly ordered). Return any one valid result while preserving the relative order of the remaining characters. Target O(n) time and O(n) or O( 1) extra space. Describe the algorithm, argue minimality, and analyze complexity. As a follow-up, discuss how to output all possible valid results if multiple exist.