How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Character.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Character during technical interviews.

Find Shortest Covering Substring | Character Coding Question

Q: Find Shortest Covering Substring

This question evaluates proficiency in string processing, handling character multiplicities, and designing time- and space-efficient algorithms for substring search.

Find Shortest Covering Substring

Company: Character

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given two strings `source` and `target`, find the shortest contiguous substring of `source` that contains every character from `target`, including duplicate occurrences. If no such substring exists, return the empty string. If multiple valid substrings have the same minimum length, return the leftmost one. You should implement an efficient algorithm and be prepared to optimize both time and space usage. Example: ```text source = "ADOBECODEBANC" target = "ABC" Output: "BANC" ``` Explanation: The substring `"BANC"` contains `A`, `B`, and `C`, and no shorter substring satisfies the requirement. Constraints: - `1 <= source.length, target.length <= 100000` - Characters may be uppercase letters, lowercase letters, digits, or symbols. - Character matching is case-sensitive.

Quick Answer: This question evaluates proficiency in string processing, handling character multiplicities, and designing time- and space-efficient algorithms for substring search.

Given two strings `source` and `target`, return the shortest contiguous substring of `source` that contains every character from `target`, including duplicate occurrences. A valid substring must contain each character at least as many times as it appears in `target`. If no such substring exists, return the empty string. If multiple valid substrings have the same minimum length, return the leftmost one. For example, with `source = "ADOBECODEBANC"` and `target = "ABC"`, the answer is `"BANC"`.

Constraints

1 <= len(source), len(target) <= 100000
Characters may be uppercase letters, lowercase letters, digits, or symbols.
Character matching is case-sensitive.
Duplicate characters in `target` must also appear with the same multiplicity in the chosen substring.

Examples

Input: ("ADOBECODEBANC", "ABC")

Expected Output: "BANC"

Explanation: "BANC" contains A, B, and C, and no shorter valid substring exists.

Input: ("AAABBC", "AABC")

Expected Output: "AABBC"

Explanation: The target needs two 'A' characters, one 'B', and one 'C'. The shortest substring that satisfies this is "AABBC".

Input: ("a", "aa")

Expected Output: ""

Explanation: The source does not contain enough 'a' characters to cover the target.

Input: ("a", "a")

Expected Output: "a"

Explanation: The single character itself is the shortest valid substring.

Input: ("aA$bb$A", "$A")

Expected Output: "A$"

Explanation: Both "A$" and "$A" are valid length-2 answers, but "A$" appears first, so it is returned.

Hints

Track how many of each character you still need, and update that information as a window expands and shrinks.
Once a window becomes valid, try moving its left edge rightward while keeping it valid to minimize its length.

Quick Overview

This question evaluates proficiency in string processing, handling character multiplicities, and designing time- and space-efficient algorithms for substring search.