Implement expression expansion to plus-only form

Given a string expression consisting only of lowercase letters (variables), '+', '', '(', and ')', return an equivalent expression that uses only '+' by fully distributing multiplication over addition. Concatenation denotes multiplication and there are no spaces. Maintain variable order within each product according to their left-to-right appearance, and output terms in the natural left-to-right expansion order. Part 1 (no '+' outside parentheses): Expand expressions where '+' appears only inside parentheses. Examples: (a+b)(c+d) -> ac+ad+bc+bd; a*(b+c)*(d+e+f)*g -> abdg+abeg+abfg+acdg+aceg+acfg. Implement an O(n) time solution using O(

1. extra space beyond the output (no stack), and explain why it works. Part 2 (general case): Expand expressions that may also contain '+' outside parentheses. Example: a+bc(d+e+f)+k+m*(g+h)+i -> a+bcd+bce+bcf+k+mg+mh+i. Implement working code that handles nested parentheses using an appropriate data structure (e.g., a stack) to track the current multiplication result segments, targeting O(n) time and O(n) extra space beyond the output. Analyze time and space complexities and discuss key edge cases.