Минимальный размер подстрок при наличии хотя бы одного символа
У меня вопрос: нужна минимальная длина k, чтобы в каждой последовательной подстроке строки длиной k должен был быть хотя бы один общий символ.
например, если s="abcaca"
для k = 1 -> подстроки — это [a], [b], [c] и т. д., поэтому мы не можем найти общий символ во всех. for k = 2 --> [ab], [bc], [ca] ... что снова нет общего символа во всех
но для k = 3 мы имеем [abc], [bca], [cac] [aca], что a и c присутствуют во всех подстроках, поэтому ответ — k.
или для s="abc" мы имеем k=2, как описано выше. мой код работает правильно, но он не оптимален для большой длины s. может ли кто-нибудь решить эту проблему с помощью динамического скользящего окна или других оптимальных способов?
n = input()
queue = list(n)
k = 1
s1 = 0
s2 = 1
last_intersection = None
sub_1 = set(queue[0:1])
while (s2 + k) < len(queue) + 1:
sub_2 = set(queue[s2: s2 + k])
if len(sub_2.intersection(sub_1)) > 0:
sub_1 = sub_2.intersection(sub_1)
s2 += 1
else:
s1 = 0
s2 = 1
k += 1
sub_1 = set(queue[s1: s1 + k])
print(k)
мы должны проверять k от 1 до тех пор, пока не дойдем до конца строки или когда у нас есть подстрока длиной k, последний символ которой является последним символом строки: например, в s = "abc" мы можем иметь 3 последовательная подстрока с k=1: 'a', 'b', 'c', и у нас может быть 2 подстроки с k=2: 'ab', 'bc', мы также можем иметь k=3, но наименьшее k, которое удовлетворяет условие задачи — k=2, потому что мы можем найти символ («b») во всех последовательных подстроках длины 2, которые можем.
Какие ограничения? Длина строки, размер алфавита?
@MBo просто размер строки от 1 до 100 000
Ответы 4
Вот логика:
s = "abcaca"
k = 1
n = len(s) # length of string s
while k < n:
a = set(s[:k])
for i in range(n - k + 1):
a &= set(s[i:i+k]) # intersection
if not a: break #if intersection is empty, no need to continue.
if a: break #if after traversing the string, intersection is not empty, break
k += 1
print(k)
3
ответ правильный, но все же я указываю превышение лимита времени для больших строк.
@AmirHossein, какова длина твоей строки?
длина от 1 до 100000
Мы можем использовать бинарный поиск для повышения эффективности:
def solve(s):
def find(k):
A = set(s[:k])
for i in range(1, n - k + 1):
A &= set(s[i:i + k])
if len(A) == 0:
return False
return True
n = len(s)
lo, hi = 1, len(s)
while lo <= hi:
mid = (lo + hi) // 2
if find(mid):
hi = mid - 1
else:
lo = mid + 1
return lo
print(solve("abcaca")) # [abc], [bca], [cac] [aca]
print(solve("abc"))
print(solve("abcacaabcdabcdeabcdeabcde"))
Принты
3
2
5
Не думайте, что эта функция поддерживает двоичный поиск.
ответ правильный, но все же я указываю превышение лимита времени для больших строк. есть ли другой способ уменьшить временную сложность?
Чтобы все подстроки содержали a, длина подстроки должна равняться максимальному расстоянию между отдельными a. То же самое для b, c и т. д.
Итак, для каждого символа алфавита найдите максимальное расстояние между его вхождениями и выберите минимальное из них. Вычисление максимальных расстояний можно выполнить за один проход по строке, а выбор минимального — за один проход по алфавиту.
Рассмотрим s = "bbaaac", правильное k равно 3, как ваш ответ может решить эту проблему?
Не забывайте о вступлении и завершении. Чтобы a появился в самой первой подстроке, она должна иметь длину 3: bba. Чтобы b появился в самой последней подстроке, она должна иметь длину 5: baaac.
я знаю, но как насчет б?? Максимальное расстояние для b равно 1, а отведение тоже равно 1, поэтому минимальное расстояние между 1, 3 и 5 равно 1, но правильный ответ – 3, или в s = ""aaab" для расстояния равно 1, а для b равно 4. , но правильный ответ 2
Не забывайте о выводе. Для b в первой строке это 4, а для a во второй — 2.
Эту проблему можно решить за линейное время по длине строки, найдя минимальное из всех максимальных расстояний между ближайшими вхождениями одного и того же символа (как также описано user58697).
Вот реализация:
def solve(s: str) -> int:
prev_idx, max_dist = {}, {}
for i, c in enumerate(s):
max_dist[c], prev_idx[c] = max(max_dist.get(c, 0), i - prev_idx.get(c, -1)), i
return min(max(d, len(s) - prev_idx[c]) for c, d in max_dist.items())
print(solve("abcaca")) # 3
print(solve("abc")) # 2
print(solve("bbaaac")) # 3
print(solve("aaab")) # 2
Спасибо, это работает в линейном времени и решает мою проблему.
@AmirHossein Рад помочь.
k может быть любым числом, и нам нужно найти минимальное значение k, при котором у нас есть общий символ в последовательных подстроках длиной k. не имеет значения, кратна ли длина строки k или нет.