Skip to content

2904. Shortest and Lexicographically Smallest Beautiful String 👍

  • Time: $O(n)$
  • Space: $O(n)$
 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
class Solution {
 public:
  // Same as 76. Minimum Window Substring
  string shortestBeautifulSubstring(string s, int k) {
    int bestLeft = -1;
    int minLength = s.length() + 1;
    int ones = 0;

    for (int l = 0, r = 0; r < s.length(); ++r) {
      if (s[r] == '1')
        ++ones;
      while (ones == k) {
        if (r - l + 1 < minLength) {
          bestLeft = l;
          minLength = r - l + 1;
        } else if (r - l + 1 == minLength &&
                   s.compare(l, minLength, s, bestLeft, minLength) < 0) {
          bestLeft = l;
        }
        if (s[l++] == '1')
          --ones;
      }
    }

    return bestLeft == -1 ? "" : s.substr(bestLeft, minLength);
  }
};

 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
class Solution {
  // Same as 76. Minimum Window Substring
  public String shortestBeautifulSubstring(String s, int k) {
    int bestLeft = -1;
    int minLength = s.length() + 1;
    int ones = 0;

    for (int l = 0, r = 0; r < s.length(); ++r) {
      if (s.charAt(r) == '1')
        ++ones;
      while (ones == k) {
        if (r - l + 1 < minLength) {
          bestLeft = l;
          minLength = r - l + 1;
        } else if (r - l + 1 == minLength &&
                   s.substring(l, l + minLength)
                           .compareTo(s.substring(bestLeft, bestLeft + minLength)) < 0) {
          bestLeft = l;
        }
        if (s.charAt(l++) == '1')
          --ones;
      }
    }

    return bestLeft == -1 ? "" : s.substring(bestLeft, bestLeft + minLength);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  # Same as 76. Minimum Window Substring
  def shortestBeautifulSubstring(self, s: str, k: int) -> str:
    bestLeft = -1
    minLength = len(s) + 1
    ones = 0

    l = 0
    for r, c in enumerate(s):
      if c == '1':
        ones += 1
      while ones == k:
        if r - l + 1 < minLength:
          bestLeft = l
          minLength = r - l + 1
        elif r - l + 1 == minLength and s[l:l + minLength] < s[bestLeft:bestLeft + minLength]:
          bestLeft = l
        if s[l] == '1':
          ones -= 1
        l += 1

    return "" if bestLeft == -1 else s[bestLeft:bestLeft + minLength]