Реши алгоритмическую задачу. Определен набор символов, из которых должен состоять…
- User
Реши алгоритмическую задачу. Определен набор символов, из которых должен состоять пароль, причём каждый символ из набора должен встречаться хотя бы один раз. Также длина пароля не превосходит k символов. В распоряжении есть последовательность символов, в которой может оказаться пароль. Формат входных данных: В первой строке ввода дана последовательность длины n (1 ≤ n ≤ 2 × 10^5) из строчных латинских букв - последовательность символов. Во второй строке дан набор символов - требования к паролю, а в третьей - число k (1 ≤ k ≤2 × 10^5), максимальная длина пароля. Формат выходных данных: Выведите возможный пароль, удовлетворяющий указанным условиям. Если вариантов пароля несколько, выберите тот, который начинается в последовательности из первой строки правее (позже) других, а среди всех с одинаковым с ним началом - самый длинный. Если восстановить пароль не удастся, выведите «-1» (без кавычек).
Примеры данных Пример 1 Ввод: abacaba abc 4 Вывод: caba Пример 2 Ввод: abacaba abc 3 Вывод: cab
- Assistant
To solve this problem efficiently, we can use a sliding window technique. We maintain a window [l..r] where
landrare left and right pointers moving through the sequence. The goal is to find the substring that contains all required characters, has a length ≤ k, starts as late as possible (with the highest possiblel), and among those, the longest possible substring.Here's how we do it:
-
Initialize required variables:
- A set of required characters from the input.
- A counter to keep track of characters in the current window.
- A variable to count the number of required characters still needed in the window.
- Variables to store the best starting position and length found so far.
-
Iterate over the sequence with the right pointer
r:- Add the current character to the window counter.
- If this character is required and hasn't been fully included yet, decrease the number of required characters needed.
-
Try to shrink the window from the left:
- While all required characters are in the window (
num_chars_needed == 0):- If the window length exceeds
k, we remove characters from the left to reduce its size. - If the window length is within
k, we update our best starting position and length if the current window starts later or is longer than the previous best. - Move the left pointer
lto the right, updating the window counter and required characters needed as necessary.
- If the window length exceeds
- While all required characters are in the window (
-
After the loop, check if a valid window was found:
- If a valid window was found (best starting position is not -1), extract the substring from the sequence and print it.
- If not, print '-1'.
Here's the implementation of the above logic:
sequence = input().strip() required = input().strip() k = int(input()) n = len(sequence) required_chars = set(required) window_counts = {} num_chars_needed = len(required_chars) l = 0 best_l = -1 best_len = 0 from collections import defaultdict window_counts = defaultdict(int) for r in range(n): ch = sequence[r] if ch in required_chars: window_counts[ch] += 1 if window_counts[ch] == 1: num_chars_needed -=1 # Try to shrink the window from the left while num_chars_needed ==0: window_len = r - l + 1 if window_len > k: # Need to move l to reduce size ch_left = sequence[l] if ch_left in required_chars: window_counts[ch_left] -=1 if window_counts[ch_left] ==0: num_chars_needed +=1 l +=1 else: # window_len ≤ k # Update best_l and best_len if l >= best_l: best_l = l best_len = window_len # Try to move l to right to find later starting point ch_left = sequence[l] if ch_left in required_chars: window_counts[ch_left] -=1 if window_counts[ch_left] ==0: num_chars_needed +=1 l +=1 if best_l != -1: print(sequence[best_l:best_l+best_len]) else: print('-1') -