Problem

You are given a binary string s and a positive integer k.

A substring of s is beautiful if the number of 1’s in it is exactly k.

Let len be the length of the shortest beautiful substring.

Return _the lexicographicallysmallest beautiful substring of string _s with length equal tolen. If s doesn’t contain a beautiful substring, return anempty string.

A string a is lexicographically larger than a string b (of the same length) if in the first position where a and b differ, a has a character strictly larger than the corresponding character in b.

  • For example, "abcd" is lexicographically larger than "abcc" because the first position they differ is at the fourth character, and d is greater than c.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
Input: s = "100011001", k = 3
Output: "11001"
Explanation: There are 7 beautiful substrings in this example:
1. The substring "_100011_ 001".
2. The substring "_1000110_ 01".
3. The substring "_10001100_ 1".
4. The substring "1 _00011001_ ".
5. The substring "10 _0011001_ ".
6. The substring "100 _011001_ ".
7. The substring "1000 _11001_ ".
The length of the shortest beautiful substring is 5.
The lexicographically smallest beautiful substring with length 5 is the substring "11001".

Example 2

1
2
3
4
5
6
7
8
Input: s = "1011", k = 2
Output: "11"
Explanation: There are 3 beautiful substrings in this example:
1. The substring "_101_ 1".
2. The substring "1 _011_ ".
3. The substring "10 _11_ ".
The length of the shortest beautiful substring is 2.
The lexicographically smallest beautiful substring with length 2 is the substring "11".

Example 3

1
2
3
Input: s = "000", k = 1
Output: ""
Explanation: There are no beautiful substrings in this example.

Constraints

  • 1 <= s.length <= 100
  • 1 <= k <= s.length

Solution

Method 1 – Sliding Window

Intuition

We want the shortest substring with exactly k ‘1’s, and among those, the lexicographically smallest. We can use a sliding window to find all substrings with exactly k ‘1’s, track the minimum length, and then among those, pick the smallest lexicographically.

Approach

  1. Use two pointers (left, right) to maintain a window and a counter for ‘1’s.
  2. Expand right, incrementing the count of ‘1’s.
  3. When the count reaches k, try to shrink the window from the left as much as possible while keeping exactly k ‘1’s.
  4. For each valid window, if its length is less than the current minimum, update the answer. If equal, update if lexicographically smaller.
  5. Return the answer after checking all windows.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    string shortestBeautifulSubstring(string s, int k) {
        int n = s.size(), cnt = 0, l = 0, minLen = n + 1;
        string ans = "";
        for (int r = 0; r < n; ++r) {
            if (s[r] == '1') ++cnt;
            while (cnt > k) {
                if (s[l++] == '1') --cnt;
            }
            if (cnt == k) {
                while (s[l] != '1') ++l;
                int len = r - l + 1;
                string sub = s.substr(l, len);
                if (len < minLen || (len == minLen && sub < ans)) {
                    minLen = len;
                    ans = sub;
                }
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func shortestBeautifulSubstring(s string, k int) string {
    n := len(s)
    cnt, l, minLen := 0, 0, n+1
    ans := ""
    for r := 0; r < n; r++ {
        if s[r] == '1' {
            cnt++
        }
        for cnt > k {
            if s[l] == '1' {
                cnt--
            }
            l++
        }
        if cnt == k {
            for s[l] != '1' {
                l++
            }
            if r-l+1 < minLen || (r-l+1 == minLen && s[l:r+1] < ans) {
                minLen = r - l + 1
                ans = s[l : r+1]
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public String shortestBeautifulSubstring(String s, int k) {
        int n = s.length(), cnt = 0, l = 0, minLen = n + 1;
        String ans = "";
        for (int r = 0; r < n; ++r) {
            if (s.charAt(r) == '1') ++cnt;
            while (cnt > k) {
                if (s.charAt(l++) == '1') --cnt;
            }
            if (cnt == k) {
                while (s.charAt(l) != '1') ++l;
                int len = r - l + 1;
                String sub = s.substring(l, r + 1);
                if (len < minLen || (len == minLen && sub.compareTo(ans) < 0)) {
                    minLen = len;
                    ans = sub;
                }
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    fun shortestBeautifulSubstring(s: String, k: Int): String {
        val n = s.length
        var cnt = 0
        var l = 0
        var minLen = n + 1
        var ans = ""
        for (r in 0 until n) {
            if (s[r] == '1') cnt++
            while (cnt > k) {
                if (s[l++] == '1') cnt--
            }
            if (cnt == k) {
                while (s[l] != '1') l++
                val len = r - l + 1
                val sub = s.substring(l, r + 1)
                if (len < minLen || (len == minLen && sub < ans)) {
                    minLen = len
                    ans = sub
                }
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def shortestBeautifulSubstring(self, s: str, k: int) -> str:
        n = len(s)
        cnt = l = 0
        min_len = n + 1
        ans = ''
        for r in range(n):
            if s[r] == '1':
                cnt += 1
            while cnt > k:
                if s[l] == '1':
                    cnt -= 1
                l += 1
            if cnt == k:
                while s[l] != '1':
                    l += 1
                length = r - l + 1
                sub = s[l:r+1]
                if length < min_len or (length == min_len and (ans == '' or sub < ans)):
                    min_len = length
                    ans = sub
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
impl Solution {
    pub fn shortest_beautiful_substring(s: String, k: i32) -> String {
        let s = s.as_bytes();
        let n = s.len();
        let mut cnt = 0;
        let mut l = 0;
        let mut min_len = n + 1;
        let mut ans = String::new();
        for r in 0..n {
            if s[r] == b'1' { cnt += 1; }
            while cnt > k {
                if s[l] == b'1' { cnt -= 1; }
                l += 1;
            }
            if cnt == k {
                while s[l] != b'1' { l += 1; }
                let len = r - l + 1;
                let sub = &s[l..=r];
                let sub_str = String::from_utf8(sub.to_vec()).unwrap();
                if len < min_len || (len == min_len && (ans.is_empty() || sub_str < ans)) {
                    min_len = len;
                    ans = sub_str;
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    shortestBeautifulSubstring(s: string, k: number): string {
        const n = s.length;
        let cnt = 0, l = 0, minLen = n + 1;
        let ans = '';
        for (let r = 0; r < n; ++r) {
            if (s[r] === '1') ++cnt;
            while (cnt > k) {
                if (s[l++] === '1') --cnt;
            }
            if (cnt === k) {
                while (s[l] !== '1') ++l;
                const len = r - l + 1;
                const sub = s.slice(l, r + 1);
                if (len < minLen || (len === minLen && (ans === '' || sub < ans))) {
                    minLen = len;
                    ans = sub;
                }
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2), where n = length of s. In the worst case, the window can move O(n) times for each right pointer.
  • 🧺 Space complexity: O(n), for storing the answer substring.