DDSA Solutions

2904. Shortest and Lexicographically Smallest Beautiful String

MediumView on LeetCode
StringSliding Window

Problem Overview

A beautiful substring has exactly k ones.

Intuition

A beautiful substring has exactly k ones. Among those, you want the shortest, and if several share that length, the lexicographically smallest. Any shortest candidate must start and end on a 1: leading zeros only make the window longer. So keep a sliding window with exactly k ones, strip leading zeros, and compare only those tight windows.

Algorithm

  1. 1Expand right. When s[r] is 1, increment ones.
  2. 2While ones > k, or ones == k and s[l] is 0, advance l (decrement ones when you drop a 1).
  3. 3When ones == k, the window [l, r] is tight. If it is shorter than the best, or the same length and lexicographically smaller, record it.
  4. 4If no window ever had k ones, return the empty string. Otherwise return the recorded substring.

Example Walkthrough

Input: s = "100011001", k = 3

  1. 1.First tight window with 3 ones is indices covering "100011001" trimmed to start/end on 1.
  2. 2.Later windows may be shorter. Among equal lengths, string.Compare picks the lex smaller start.
  3. 3.One valid shortest answer is "11001".

Output: "11001"

Common Pitfalls

  • •Do not compare windows that still have a leading 0. They are never shortest.
  • •Exactly k ones, not at least k. Shrinking past an extra 1 is required when ones exceeds k.
  • •If the string has fewer than k ones, return "".
  • •On equal length, compare the substrings themselves, not only their start indices.
2904.cs
C#
// Approach: Sliding window on exactly k ones. Shrink while ones > k or the
// window has a leading zero, so every candidate starts and ends on a 1.
// Track the shortest window; on ties keep the lexicographically smaller one.
// Complexity: O(n * L) time in the worst case for string compares (L = answer
// length), O(1) extra space.
public class Solution
{
    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[r] == '1')
                ++ones;

            while (ones > k || (ones == k && s[l] == '0'))
            {
                if (s[l++] == '1')
                    --ones;
            }

            if (ones == k)
            {
                int currentLength = r - l + 1;
                if (currentLength < minLength ||
                    (currentLength == minLength && string.Compare(s, l, s, bestLeft, minLength) < 0))
                {
                    bestLeft = l;
                    minLength = currentLength;
                }
            }
        }

        return bestLeft == -1 ? "" : s.Substring(bestLeft, minLength);
    }
}
Was this solution helpful?

Related Problems