Skip to content

2904. Shortest and Lexicographically Smallest Beautiful String

Description

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 lexicographically smallest beautiful substring of string s with length equal to len. If s doesn't contain a beautiful substring, return an empty 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.

 

Example 1:

Input: s = "100011001", k = 3
Output: "11001"
Explanation: There are 7 beautiful substrings in this example:
1. The substring "100011001".
2. The substring "100011001".
3. The substring "100011001".
4. The substring "100011001".
5. The substring "100011001".
6. The substring "100011001".
7. The substring "100011001".
The length of the shortest beautiful substring is 5.
The lexicographically smallest beautiful substring with length 5 is the substring "11001".

Example 2:

Input: s = "1011", k = 2
Output: "11"
Explanation: There are 3 beautiful substrings in this example:
1. The substring "1011".
2. The substring "1011".
3. The substring "1011".
The length of the shortest beautiful substring is 2.
The lexicographically smallest beautiful substring with length 2 is the substring "11".

Example 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

Solutions

Solution 1: Enumeration

Thinking

A beautiful substring contains exactly \(k\) ones. \(n \le 100\) lets us enumerate all \(O(n^2)\) substrings and count ones. Among valid pieces, keep the shorter one, breaking ties by lexicographic order.

The inner scan may start at \(i+k\), since at least \(k\) characters are needed to hold \(k\) ones.

We can enumerate all substrings \(s[i: j]\), where \(i \lt j\), and check if they are beautiful substrings. If so, we update the answer.

The time complexity is \(O(n^3)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the string \(s\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def shortestBeautifulSubstring(self, s: str, k: int) -> str:
        n = len(s)
        ans = ""
        for i in range(n):
            for j in range(i + k, n + 1):
                t = s[i:j]
                if t.count("1") == k and (
                    not ans or j - i < len(ans) or (j - i == len(ans) and t < ans)
                ):
                    ans = t
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public String shortestBeautifulSubstring(String s, int k) {
        int n = s.length();
        String ans = "";
        for (int i = 0; i < n; ++i) {
            for (int j = i + k; j <= n; ++j) {
                String t = s.substring(i, j);
                int cnt = 0;
                for (char c : t.toCharArray()) {
                    cnt += c - '0';
                }
                if (cnt == k
                    && ("".equals(ans) || j - i < ans.length()
                        || (j - i == ans.length() && t.compareTo(ans) < 0))) {
                    ans = t;
                }
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    string shortestBeautifulSubstring(string s, int k) {
        int n = s.size();
        string ans = "";
        for (int i = 0; i < n; ++i) {
            for (int j = i + k; j <= n; ++j) {
                string t = s.substr(i, j - i);
                int cnt = count(t.begin(), t.end(), '1');
                if (cnt == k && (ans == "" || j - i < ans.size() || (j - i == ans.size() && t < ans))) {
                    ans = t;
                }
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func shortestBeautifulSubstring(s string, k int) (ans string) {
    n := len(s)
    for i := 0; i < n; i++ {
        for j := i + k; j <= n; j++ {
            t := s[i:j]
            cnt := 0
            for _, c := range t {
                if c == '1' {
                    cnt++
                }
            }
            if cnt == k && (ans == "" || j-i < len(ans) || (j-i == len(ans) && t < ans)) {
                ans = t
            }
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function shortestBeautifulSubstring(s: string, k: number): string {
    const n = s.length;
    let ans: string = '';
    for (let i = 0; i < n; ++i) {
        for (let j = i + k; j <= n; ++j) {
            const t = s.slice(i, j);
            const cnt = t.split('').filter(c => c === '1').length;
            if (
                cnt === k &&
                (ans === '' || j - i < ans.length || (j - i === ans.length && t < ans))
            ) {
                ans = t;
            }
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
impl Solution {
    pub fn shortest_beautiful_substring(s: String, k: i32) -> String {
        let n = s.len();
        let mut ans = String::new();

        for i in 0..n {
            for j in i + (k as usize)..=n {
                let t = &s[i..j];
                if (t.matches('1').count() as i32) == k
                    && (ans.is_empty() || j - i < ans.len() || (j - i == ans.len() && t < &ans))
                {
                    ans = t.to_string();
                }
            }
        }
        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
public class Solution {
    public string ShortestBeautifulSubstring(string s, int k) {
        int n = s.Length;
        string ans = "";

        for (int i = 0; i < n; i++) {
            for (int j = i + k; j <= n; j++) {
                string t = s.Substring(i, j - i);

                int cnt = 0;
                foreach (char c in t.ToCharArray()) {
                    cnt += c - '0';
                }

                if (cnt == k &&
                    (ans == "" ||
                     j - i < ans.Length ||
                     (j - i == ans.Length && string.Compare(t, ans, StringComparison.Ordinal) < 0))) {
                    ans = t;
                }
            }
        }

        return ans;
    }
}

Solution 2: Two Pointers

Thinking

Enumeration is acceptable at \(n=100\), yet calling \(count\) on every slice rescans the same range. Beautiful pieces are windows with exactly \(k\) ones; dropping a leading \(0\) does not lose a one, so a shortest candidate has no leading zero.

Two pointers maintain the window: extend the right end, and shrink while the one-count exceeds \(k\) or the left character is \(0\). Whenever the count equals \(k\), compare length and lexicographic order with the current answer.

We can also use two pointers to maintain a sliding window, where pointer \(i\) points to the left boundary of the window, and pointer \(j\) points to the right boundary of the window. Initially, \(i\) and \(j\) both point to \(0\). In addition, we use a variable \(cnt\) to record the number of \(1\)s in the sliding window.

We first move pointer \(j\) to the right, add \(s[j]\) to the sliding window, and update \(cnt\). If \(cnt\) is greater than \(k\), or if \(i\) is less than \(j\) and \(s[i]\) is \(0\), we move pointer \(i\) to the right and update \(cnt\).

When \(cnt\) equals \(k\), we have found a beautiful substring. We compare it with the current answer and update the answer if necessary.

The time complexity is \(O(n^2)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the string \(s\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def shortestBeautifulSubstring(self, s: str, k: int) -> str:
        i = j = cnt = 0
        n = len(s)
        ans = ""
        while j < n:
            cnt += s[j] == "1"
            while cnt > k or (i < j and s[i] == "0"):
                cnt -= s[i] == "1"
                i += 1
            j += 1
            if cnt == k and (
                not ans or j - i < len(ans) or (j - i == len(ans) and s[i:j] < ans)
            ):
                ans = s[i:j]
        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 i = 0, j = 0, cnt = 0;
        int n = s.length();
        String ans = "";
        while (j < n) {
            cnt += s.charAt(j) - '0';
            while (cnt > k || (i < j && s.charAt(i) == '0')) {
                cnt -= s.charAt(i) - '0';
                ++i;
            }
            ++j;
            String t = s.substring(i, j);
            if (cnt == k
                && ("".equals(ans) || j - i < ans.length()
                    || (j - i == ans.length() && t.compareTo(ans) < 0))) {
                ans = t;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    string shortestBeautifulSubstring(string s, int k) {
        int i = 0, j = 0, cnt = 0;
        int n = s.size();
        string ans = "";
        while (j < n) {
            cnt += s[j] == '1';
            while (cnt > k || (i < j && s[i] == '0')) {
                cnt -= s[i++] == '1';
            }
            ++j;
            string t = s.substr(i, j - i);
            if (cnt == k && (ans == "" || j - i < ans.size() || (j - i == ans.size() && t < ans))) {
                ans = t;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func shortestBeautifulSubstring(s string, k int) (ans string) {
    i, j, cnt := 0, 0, 0
    n := len(s)
    for j < n {
        cnt += int(s[j] - '0')
        for cnt > k || (i < j && s[i] == '0') {
            cnt -= int(s[i] - '0')
            i++
        }
        j++
        t := s[i:j]
        if cnt == k && (ans == "" || j-i < len(ans) || (j-i == len(ans) && t < ans)) {
            ans = t
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function shortestBeautifulSubstring(s: string, k: number): string {
    let [i, j, cnt] = [0, 0, 0];
    const n = s.length;
    let ans: string = '';
    while (j < n) {
        cnt += s[j] === '1' ? 1 : 0;
        while (cnt > k || (i < j && s[i] === '0')) {
            cnt -= s[i++] === '1' ? 1 : 0;
        }
        ++j;
        const t = s.slice(i, j);
        if (cnt === k && (ans === '' || j - i < ans.length || (j - i === ans.length && t < ans))) {
            ans = t;
        }
    }
    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
29
30
31
32
33
impl Solution {
    pub fn shortest_beautiful_substring(s: String, k: i32) -> String {
        let s_chars: Vec<char> = s.chars().collect();
        let mut i = 0;
        let mut j = 0;
        let mut cnt = 0;
        let mut ans = String::new();
        let n = s.len();

        while j < n {
            if s_chars[j] == '1' {
                cnt += 1;
            }

            while cnt > k || (i < j && s_chars[i] == '0') {
                if s_chars[i] == '1' {
                    cnt -= 1;
                }
                i += 1;
            }

            j += 1;

            if cnt == k
                && (ans.is_empty() || j - i < ans.len() || (j - i == ans.len() && &s[i..j] < &ans))
            {
                ans = s_chars[i..j].iter().collect();
            }
        }

        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
29
public class Solution {
    public string ShortestBeautifulSubstring(string s, int k) {
        int i = 0, j = 0, cnt = 0;
        int n = s.Length;
        string ans = "";

        while (j < n) {
            cnt += s[j] - '0';

            while (cnt > k || (i < j && s[i] == '0')) {
                cnt -= s[i] - '0';
                i++;
            }

            j++;

            string t = s.Substring(i, j - i);

            if (cnt == k &&
                (ans == "" ||
                 j - i < ans.Length ||
                 (j - i == ans.Length && string.Compare(t, ans, StringComparison.Ordinal) < 0))) {
                ans = t;
            }
        }

        return ans;
    }
}

Comments