Solve two string algorithm tasks

Q: Solve two string algorithm tasks

This question evaluates string algorithm skills — specifically parentheses balancing and shortest covering-substring problems — testing linear-time algorithm design, frequency tracking, and handling of large input-size constraints in the coding & algorithms domain.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Answer both parts. A) Parentheses correction: Given a string s consisting only of '(' and ')', output the minimum number of parentheses you must insert (at any positions) to make s a valid balanced parentheses string. Define validity in the usual way via matching pairs and proper nesting. Constraints: 1 <= |s| <= 100,000. Describe an O(n)-time algorithm with O(

or O(n) extra space and briefly justify correctness. B) Shortest covering substring: Given two strings s and t (ASCII), return the shortest contiguous substring of s that contains every character of t at least as many times as it appears in t; if no such substring exists, return the empty string. If multiple answers have the same length, return any. Constraints: 1 <= |s| <= 200,000; 1 <= |t| <= 10,000. Provide the algorithm, time and space complexities, and key edge cases.

Solve two string algorithm tasks

Overview

Comments (0)