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.
"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 <= 1001 <= k <= s.length문자열, 슬라이딩 윈도우
이 문제는 이진 문자열 s와 정수 k가 주어졌을 때, '1'의 개수가 정확히 k개인 가장 짧은 부분 문자열을 찾는 것입니다. 만약 그러한 부분 문자열이 여러 개 있다면, 그중에서 **사전순으로 가장 작은 것(lexicographically smallest)**을 반환해야 합니다. 조건을 만족하는 부분 문자열이 없으면 빈 문자열을 반환합니다.
s (길이 1 ~ 100), 정수 k (1 ~ s.length)이 문제는 슬라이딩 윈도우(Sliding Window) 기법을 사용하여 해결합니다.
left, right)를 이용해 윈도우를 확장/축소하며 효율적으로 탐색할 수 있습니다.right 포인터를 오른쪽으로 이동하며 윈도우를 확장하고, '1'의 개수(cnt)를 셉니다.cnt가 k와 같아지면(아름다운 문자열 후보 발견), left 포인터를 오른쪽으로 이동하며 윈도우를 최소 길이로 축소합니다. 이때 left가 가리키는 문자가 '1'이면 cnt가 줄어들어 조건이 깨지므로 루프를 종료합니다.cnt == k)을 만족하는 모든 부분 문자열을 후보 리스트에 저장합니다.left, right: 슬라이딩 윈도우의 시작과 끝을 가리키는 포인터로, 둘 다 0에서 시작합니다.cnt: 현재 윈도우 내 '1'의 개수를 저장하는 카운터입니다.answer: 조건을 만족하는 아름다운 부분 문자열들을 저장할 리스트입니다.while right != len(s))right가 문자열 끝까지 도달할 때까지 반복합니다.s[right]가 '1'이면 cnt를 1 증가시킵니다.while k == cnt)k개 들어있으면(k == cnt), 내부 루프를 실행합니다.s[left]가 '1'인 경우에만 s[left:right+1]을 answer에 추가합니다.left가 '0'이라면 왼쪽에 불필요한 '0'이 있는 것이므로 최소 길이가 아닙니다. left가 '1'일 때가 해당 윈도우에서 '1' k개를 유지하며 만들 수 있는 가장 짧은 길이입니다.s[left]가 '1'이면 cnt를 감소시키고(조건 깨짐 예고), left를 오른쪽으로 이동시킵니다. cnt가 k 미만이 되면 루프를 빠져나옵니다.answer 리스트를 정렬합니다. 정렬 키는 (길이, 문자열 자체)로 하여 길이가 짧은 순서대로, 길이가 같으면 사전순으로 정렬되도록 합니다.answer가 비어있지 않으면 첫 번째 원소(answer[0])를, 비어있으면 빈 문자열("")을 반환합니다.left, right가 각각 최대 N번 이동하므로 **O(N)**입니다.s[left:right+1] 슬라이싱 연산이 발생하는데, 파이썬에서 문자열 슬라이싱은 O(부분 문자열 길이) 시간이 걸립니다. 최악의 경우(모든 문자가 '1'인 경우) O(N^2)개의 후보가 생기고 각각 O(N) 시간이 걸려 **O(N^3)**이 될 수 있습니다.O(M log M) 비교가 발생하며, 문자열 비교는 최악의 경우 O(N)입니다.s.length <= 100)이 매우 작아 실제 실행 시간에는 문제가 없습니다.right로 확장하며 개수를 채우고, left로 축소하며 최소 길이를 찾는 투 포인터 패턴을 사용했습니다.while k == cnt 루프 내부에서 s[left] == '1'일 때만 후보로 저장하고 left를 이동시킵니다. 이는 현재 윈도우에서 왼쪽의 불필요한 '0'을 모두 제거하고, '1'을 만나기 직전(즉, '1'을 포함하는) 상태가 가장 짧은 길이임을 이용한 것입니다.answer.sort(key=lambda x: (len(x), x)) 한 줄로 '길이 오름차순 -> 사전순 오름차순'이라는 복합 정렬 조건을 간결하고 정확하게 구현했습니다.class Solution:
def shortestBeautifulSubstring(self, s: str, k: int) -> str:
left = 0
right = 0
cnt = 0
answer = []
while right != len(s):
if s[right] == "1":
cnt += 1
while k == cnt:
if k == cnt and s[left] == "1":
answer.append(s[left:right+1])
if s[left] == "1":
cnt -= 1
left += 1
right += 1
answer.sort(key = lambda x:(len(x),x))
return answer[0] if answer else ""