Строки — AlgoTasks

125.

Valid Palindrome

Easy строки два указателя

Дана строка s. Проверьте, является ли она палиндромом, игнорируя регистр букв и все неалфавитно-цифровые символы. Буквы — латинские, цифры обычные.

Ограничения: 1 ≤ s.length ≤ 2·10⁵.

Пример 1

s = "A man, a plan, a canal: Panama"
output = true        # "amanaplanacanalpanama"

Пример 2

s = "race a car"
output = false

Пример 3

s = " "
output = true        # пустая строка считается палиндромом

Подсказка

Не обязательно строить «очищенную» строку. Поставьте два указателя с краёв, двигайте их, пропуская «мусорные» символы, и сравнивайте символы в нижнем регистре.

Решение

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

Сложность: время O(n), память O(1).

Похожая задача на LeetCode: 680. Valid Palindrome II (Easy) — разрешён ровно один «пропуск» символа.

3.

Longest Substring Without Repeating Characters

Medium строки скользящее окно хэш-таблица

Дана строка s. Найдите длину самой длинной подстроки без повторяющихся символов. Подстрока — непрерывный кусок строки.

Ограничения: 0 ≤ s.length ≤ 5·10⁴, символы — ASCII.

Пример 1

s = "abcabcbb"
output = 3           # "abc"

Пример 2

s = "bbbbb"
output = 1           # "b"

Пример 3

s = "pwwkew"
output = 3           # "wke"; "pwke" — не подстрока, а подпоследовательность

Подсказка

Держите окно [left..right], в котором все символы уникальны. Храните последний индекс каждого символа: при повторе не сдвигайте left по одному, а перепрыгните сразу за прошлое вхождение.

Решение

def length_of_longest_substring(s):
    last = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1      # прыжок за прошлое вхождение
        last[ch] = right
        best = max(best, right - left + 1)
    return best

Сложность: время O(n), память O(min(n, |алфавит|)).

20.

Valid Parentheses

Easy строки стек

Дана строка s, содержащая только символы ()[]{}. Определите, корректна ли строка: открывающие скобки должны закрываться скобками того же типа и в правильном порядке.

Ограничения: 1 ≤ s.length ≤ 10⁴.

Пример 1

s = "()"      → true
s = "()[]{}"  → true
s = "(]"      → false

Пример 2

s = "([)]"    → false
s = "{[]}"    → true
s = "("       → false

Подсказка

Последняя открытая скобка должна закрыться первой — это LIFO, то есть стек. Открывающую — кладём, закрывающую — сверяем с вершиной стека.

Решение

def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in pairs:                     # закрывающая
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:                               # открывающая
            stack.append(ch)
    return not stack                        # не осталось открытых

Сложность: время O(n), память O(n) в худшем случае.

Продолжение темы: 921. Minimum Add to Make Parentheses Valid (Medium) — сколько скобок нужно добавить, чтобы строка стала корректной.

443.

Дан массив символов chars. Сожмите его «на месте»: каждая серия одинаковых символов заменяется на сам символ и, если длина серии больше 1, на цифры этой длины. Использовать дополнительную память нельзя, верните новую длину массива.

Ограничения: 1 ≤ chars.length ≤ 2000, память O(1).

Пример 1

chars = ["a","a","b","b","c","c","c"]
output = 6, первые 6 элементов: ["a","2","b","2","c","3"]

Пример 2

chars = ["a","a","a","a","a","a","b","b","a","a"]
output = 6, первые 6 элементов: ["a","6","b","2","a","2"]

Подсказка

Два указателя: read идёт по массиву и считает серию, write пишет символ и (если нужно) цифры длины. Числа вроде 12 занимают два элемента — пишите посимвольно.

Решение

def compress(chars):
    write = read = 0
    n = len(chars)
    while read < n:
        ch = chars[read]
        count = 0
        while read < n and chars[read] == ch:
            read += 1
            count += 1
        chars[write] = ch
        write += 1
        if count > 1:                       # длину пишем посимвольно
            for d in str(count):
                chars[write] = d
                write += 1
    return write

Сложность: время O(n), память O(1).

Ближайшая задача LeetCode: 443. String Compression (Medium) — там сжатие делается «на месте» в массиве символов.

392.

Is Subsequence

Easy строки два указателя

Даны строки s и t. Проверьте, является ли s подпоследовательностью t: то есть получается ли s из t удалением некоторых символов без изменения порядка оставшихся.

Ограничения: 0 ≤ s.length ≤ 100, 1 ≤ t.length ≤ 10⁵.

Пример 1

s = "abc", t = "ahbgdc"
output = true

Пример 2

s = "axc", t = "ahbgdc"
output = false

Подсказка

Жадный алгоритм корректен: идите по t и «сверяйте» символы s по порядку. Если дошли до конца s — ответ true.

Решение

def is_subsequence(s, t):
    i = 0
    for ch in t:
        if i < len(s) and s[i] == ch:
            i += 1
    return i == len(s)

Сложность: время O(|t|), память O(1).

Follow-up (LeetCode 2): если приходит много строк-запросов, предварительно постройте для t словарь «символ → список позиций» и ищите бинарным поиском — получится O(|s| · log|t|) на запрос.