▲

3

▼

🌀 Поиск уникальных палиндромов длины 3 с использованием битового массива

leetcoder, 04-01-2025 , 563

Наша очередная задача - 1930. Unique Length-3 Palindromic Subsequences.

📝 Описание задачи

Дана строка s. Необходимо определить количество уникальных палиндромов длины 3, которые являются подпоследовательностями строки.

Подпоследовательность — это строка, полученная из исходной строки удалением некоторых (возможно, нуля) символов без изменения их порядка. Например, для строки "abcde" строка "ace" является подпоследовательностью.

Палиндром — это строка, которая читается одинаково в прямом и обратном направлениях.

💡 Идея

Основная идея заключается в том, что палиндром длины 3 определяется первыми и последними символами, которые совпадают, а также любым допустимым символом посередине.
Мы можем эффективно отслеживать такие пары (первый и последний символы) с помощью битового массива (bitset), что позволяет минимизировать использование памяти.

🔍 Детали подхода

1. Массивы частот:
   • prefix_frequency: хранит частоты символов слева от рассматриваемого.
   • suffix_frequency: хранит частоты символов справа от рассматриваемого.
2. Битовый массив для встреченных палиндромов:
   • Используем массив u32, где каждое число, рассматриваемое как битовое множество, кодирует возможные палиндромы (по сути, крайние символы) для рассматриваемого символа посередине.
3. Обход строки: Для каждого символа:
   • Обновляем массивы частот.
   • Проверяем все возможные крайние символы (используя prefix_frequency и suffix_frequency) и обновляем битовый массив, если символ допустим.
4. Подсчёт уникальных палиндромов:
   • Суммируем количество установленных битов в массиве битовых массивов, чтобы получить общее количество уникальных палиндромов.

⏱ Асимптотика

• Временная сложность: O(n)
  • Для каждого символа проверяем 26 возможных символов для пары (первый и последний).
• Пространственная сложность: O(1)
  • Используем массивы для хранения частот и битовый массив размером 26.

💻 Исходный код

impl Solution {
    pub fn count_palindromic_subsequence(s: String) -> i32 {
        const ALPHABET_SIZE: usize = 26;

        // Step 1: Suffix frequency tracking
        let mut suffix_frequency = vec![0; ALPHABET_SIZE];
        for &c in s.as_bytes() {
            suffix_frequency[(c - b'a') as usize] += 1;
        }

        let mut prefix_frequency = vec![0; ALPHABET_SIZE];
        let mut seen_palindromes = vec![0u32; ALPHABET_SIZE]; // Bitset for each character pair

        // Step 2: Traverse characters
        for &c in s.as_bytes() {
            let index = (c - b'a') as usize;
            suffix_frequency[index] -= 1;

            let mut val = seen_palindromes[index];
            for i in 0..ALPHABET_SIZE {
                let mask = 1 << i;
                // Check if the bit is unset and the pair forms a valid palindrome
                if (val & mask) == 0 && prefix_frequency[i] > 0 && suffix_frequency[i] > 0 {
                    val |= mask; // Set the bit for the pair (index, i)
                }
            }
            seen_palindromes[index] = val;

            prefix_frequency[index] += 1;
        }

        // Step 3: Count unique palindromes
        seen_palindromes.iter().map(|&bits| bits.count_ones() as i32).sum()
    }
}