Shortest Substring with Exactly k Ones and Lexicographic Ties
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Shortest Substring with Exactly k Ones and Lexicographic Ties
You are given a binary string `s` and a positive integer `k`. A beautiful substring is a contiguous substring containing exactly `k` occurrences of `'1'`.
First minimize the length of a beautiful substring. Among all beautiful substrings of that minimum length, return the lexicographically smallest one. If no beautiful substring exists, return the empty string `""`.
For two equal-length strings, lexicographic order is determined by their first differing character; `'0'` comes before `'1'`.
### Examples
**Example 1**
```text
Input: s = "1101011", k = 3
Output: "1011"
```
The shortest candidates have length `4`: `"1101"` at indices `0..3` and `"1011"` at indices `3..6`. No length-three substring is `"111"`, so no shorter substring contains three ones. At the second character, `"1011"` has `'0'` while `"1101"` has `'1'`, so `"1011"` wins the tie.
**Example 2**
```text
Input: s = "0100", k = 2
Output: ""
```
The entire string contains only one `'1'`, so no substring contains exactly two ones.
### Constraints
- `1 <= s.length <= 100`.
- `1 <= k <= s.length`.
- `s` is a binary string, containing only `'0'` and `'1'`.
### Clarifying Questions
- Is the length or lexicographic order more important? Length comes first; lexicographic order breaks ties between equally short candidates.
- Is a subsequence allowed? No; the returned characters must occupy one contiguous interval in `s`.
- Does a substring with more than `k` ones qualify? No; the count must be exactly `k`.
- Can different positions yield the same candidate string? Yes; return the string itself, so identical candidate values require no further tie rule.
- Can the empty string be a qualifying substring? No, since `k` is positive. It is only the specified result when no qualifying substring exists.
### C++ Interface
```cpp
class Solution {
public:
string shortestBeautifulSubstring(string s, int k) {
}
};
```
### Reasoning Checkpoints
- Enforce contiguity and the exact count of ones.
- Apply the two optimization criteria in the specified order.
- Cover repeated candidate strings and the absence of any valid substring.
```hint One candidate endpoint per start
For a fixed left endpoint, scan until the kth one appears. Any later endpoint with the same count is longer. Compare this earliest qualifying candidate with the best candidate from other left endpoints.
```
Overview: Return the shortest contiguous binary substring containing exactly k ones, break equal-length ties lexicographically, and return an empty string when none exists.
