План курса / Все задачи / Алгоритмы и структуры данных
Цепочка уникальных генов
средне
# решено
Дана строка gene, представляющая последовательность генов, где каждый ген — это одна буква английского алфавита.
Требуется найти самую длинную непрерывную подстроку, в которой все гены уникальны (без повторяющихся букв).
Пример 1:
Ввод: gene = "yxyabcxyx"
Вывод: 5
Объяснение: "xyabc" или "yabcx" или "abcxy" самые длинные подстроки с длинной 5.
Пример 2:
Ввод: gene = "Aac"
Вывод: 3
Пример 3:
Ввод: gene = "ffff"
Вывод: 1
Ограничения:
0 <= len(gene)
Строка gene может быть содержать только английские буквы
public class Solution
{
public static int LongestGeneSequence(string gene)
{
// Коллекция уникальных генов в окне
HashSet<char> geneUnique = new HashSet<char>();
int l = 0, r = -1;
int windowSize = 0, result = 0;
while (l < gene.Length)
{
while (r + 1 < gene.Length && !geneUnique.Contains(gene[r + 1]))
{
geneUnique.Add(gene[r + 1]);
r++;
}
// Обновляем ответ
windowSize = r - l + 1;
result = Math.Max(result, windowSize);
// Удаляем символ, который выходит из окна
geneUnique.Remove(gene[l]);
l++;
}
return result;
}
}
#include <unordered_set>
#include <algorithm>
using namespace std;
int longestGeneSequence(const string& gene) {
// коллекция уникальных генов в окне
unordered_set<char> geneUnique;
int l = 0, r = -1;
int windowSize = 0, result = 0;
while (l < gene.length()) {
while (r + 1 < gene.length() && geneUnique.count(gene[r + 1]) == 0) {
geneUnique.insert(gene[r + 1]);
r++;
}
// обновляем ответ
windowSize = r - l + 1;
result = max(result, windowSize);
// удаляем символ, который выходит из окна
geneUnique.erase(gene[l]);
l++;
}
return result;
}
package main
func longestGeneSequence(gene string) int {
// коллекция уникальных генов в окне
geneUnique := make(map[byte]bool)
l, r := 0, -1
windowSize, result := 0, 0
for l < len(gene) {
for r+1 < len(gene) && !geneUnique[gene[r+1]] {
geneUnique[gene[r+1]] = true
r++
}
// обновляем ответ
windowSize = r - l + 1
if windowSize > result {
result = windowSize
}
// удаляем символ, который выходит из окна
delete(geneUnique, gene[l])
l++
}
return result
}
import java.util.*;
public class Solution {
public int longestGeneSequence(String gene) {
// коллекция уникальных генов в окне
HashSet<Character> geneUnique = new HashSet<>();
int l = 0, r = -1;
int windowSize = 0, result = 0;
while (l < gene.length()) {
while (r + 1 < gene.length() && !geneUnique.contains(gene.charAt(r + 1))) {
geneUnique.add(gene.charAt(r + 1));
r++;
}
// обновляем ответ
windowSize = r - l + 1;
result = Math.max(result, windowSize);
// удаляем символ, который выходит из окна
geneUnique.remove(gene.charAt(l));
l++;
}
return result;
}
}
from typing import *
def longest_gene_sequence(gene: str) -> int:
# коллекция уникальных генов в окне
gene_unique = set()
l, r = 0, -1
window_size, result = 0, 0
while l < len(gene):
while r + 1 < len(gene) and gene[r + 1] not in gene_unique:
gene_unique.add(gene[r + 1])
r += 1
# обновляем ответ
window_size = r - l + 1
result = max(result, window_size)
# удаляем символ, который выходит из окна
gene_unique.discard(gene[l])
l += 1
return result
/**
* @param {string} gene
* @returns {number}
*/
export function longestGeneSequence(gene) {
// коллекция уникальных генов в окне
const geneUnique = new Set();
let l = 0, r = -1;
let windowSize = 0, result = 0;
while (l < gene.length) {
while (r + 1 < gene.length && !geneUnique.has(gene[r + 1])) {
geneUnique.add(gene[r + 1]);
r++;
}
// обновляем ответ
windowSize = r - l + 1;
result = Math.max(result, windowSize);
// удаляем символ, который выходит из окна
geneUnique.delete(gene[l]);
l++;
}
return result;
}
Оценка сложности
Время: O(n), где n - длина строки gene
Память: O(min(n, m)), где m — количество уникальных символов