▲

3

▼

💡 Генерация k-ой счастливой строки через двоичное представление

leetcoder, 19-02-2025 , 71

Ссылка на задачу — 1415. The k-th Lexicographical String of All Happy Strings of Length n.

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

"Счастливая строка" – это строка длины n, состоящая только из символов ['a', 'b', 'c'], в которой нет двух одинаковых подряд идущих символов.
Нужно найти k-ю счастливую строку в лексикографическом порядке, либо вернуть "", если таких строк меньше k.

💡 Идея

Рассмотрим связь счастливых строк с двоичными строками.
Каждая счастливая строка:

• Начинается с одного из трёх символов ('a', 'b', 'c') → 3 варианта.
• Остальные (n-1) символов формируются по аналогии с двоичной строкой, где у каждого символа есть ровно два возможных варианта → ×2 на каждую позицию.

Таким образом, двоичное представление k-1 почти полностью определяет структуру требуемой строки (без первого символа).
Мы можем использовать биты 0 и 1 из этого двоичного представления, чтобы выбирать между двумя допустимыми символами при итеративной генерации каждого следующего символа конкретной счастливой строки. 🚀

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

1. Определяем количество возможных строк с фиксированным первым символом:
   • happy_count = 2n−1
   • Это число показывает, сколько строк начинается с 'a', 'b' или 'c'.
2. Выбираем первый символ по значению (k-1) / happy_count:
   • (k-1) / happy_count = 0 → 'a'
   • (k-1) / happy_count = 1 → 'b'
   • (k-1) / happy_count = 2 → 'c'
3. Используем следующие биты из двоичной формы k-1 для выбора последующих символов:
   Каждый бит (0 или 1) управляет выбором между двумя возможными символами, исключая повтор предыдущего.
   • Если бит = 0, выбираем меньший допустимый символ.
   • Если бит = 1, выбираем больший допустимый символ.
4. Возвращаем итоговую строку. 🚀

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

• Временная сложность: O(n), так как проходим строку ровно один раз.
• Дополнительная память: O(n), для генерируемой строки-результата.

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

impl Solution {
    pub fn get_happy_string(n: i32, k: i32) -> String {
        let mut result = String::with_capacity(n as usize);
        let mut k = k - 1; // Convert to zero-based index
        let happy_count = 1 << (n - 1); // Number of happy strings with a fixed first character

        // Determine the first character
        let first_char = match k / happy_count {
            0 => 'a',
            1 => 'b',
            2 => 'c',
            _ => return "".to_string(), // Not enough happy strings exist
        };
        result.push(first_char);
        k %= happy_count; // Update k to determine the remaining characters

        // Construct the happy string
        for i in (0..n - 1).rev() {
            let prev_char = result.chars().last().unwrap();
            let happy_count = 1 << i; // Number of happy strings with a fixed prefix of length n-i

            let mut next_char = Self::adjust_char('a', prev_char);
            if k >= happy_count {
                next_char = Self::adjust_char(((next_char as u8) + 1) as char, prev_char);
                k -= happy_count;
            }
            result.push(next_char);
        }

        result
    }

    // Ensure that the selected character is different from the previous one
    fn adjust_char(candidate: char, prev_char: char) -> char {
        if candidate == prev_char {
            return ((candidate as u8) + 1) as char; // Move to the next valid character
        }
        candidate
    }
}

Tags: #rust #algorithms #strings