LeetCode Entry

3163. String Compression III

04.11.2024 medium 2024 kotlin rust

Compress repeating chars in string pointers

3163. String Compression III medium blog post substack youtube deep-dive

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/790

Problem TLDR

Compress repeating chars in string #medium #two_pointers

Intuition

This is all about how you implement it. One way is to use a counter and analyze the current position. Another way is to use the two pointers and skip all the repeating characters making a single point of appending.

Approach

• Rust has a cool chunk_by method

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(n)\)

Code

    fun compressedString(word: String) = buildString {
        var j = 0; var i = 0
        while (i < word.length) {
            while (j < min(i + 9, word.length)
                   && word[i] == word[j]) j++
            append("${j - i}${word[i]}")
            i = j
        }
    }

    pub fn compressed_string(word: String) -> String {
        word.into_bytes().chunk_by(|a, b| a == b)
        .flat_map(|ch| ch.chunks(9).flat_map(|c|
            [(b'0' + c.len() as u8) as char, c[0].into()])
        ).collect()
    }

    string compressedString(string w) {
        string r;
        for(int i = 0, j = 0; i < size(w); i = j) {
            for(; j < i + 9 && j < size(w) && w[i] == w[j]; ++j);
            r += 48 + j - i; r += w[i];
        }
        return r;
    }