Constraints

• mode is either 'compress' or 'decompress'.
• For compression, 0 <= len(text) <= 100000.
• For compression, text contains printable ASCII characters excluding digits '0'..'9'.
• For decompression, text is well-formed as zero or more groups of <positive integer><single non-digit character>.
• Counts fit in a standard integer type, and the fully decoded output length is at most 1000000.

Examples

Solution

def solution(mode, text):
    if mode not in ('compress', 'decompress'):
        raise ValueError("mode must be 'compress' or 'decompress'")

    if mode == 'compress':
        if text == '':
            return ''

        result = []
        count = 1

        for i in range(1, len(text) + 1):
            if i < len(text) and text[i] == text[i - 1]:
                count += 1
            else:
                result.append(str(count))
                result.append(text[i - 1])
                count = 1

        return ''.join(result)

    # mode == 'decompress'
    if text == '':
        return ''

    result = []
    digits = []

    for ch in text:
        if ch.isdigit():
            digits.append(ch)
        else:
            if not digits:
                raise ValueError('Invalid encoded string')
            count = int(''.join(digits))
            if count <= 0:
                raise ValueError('Invalid encoded string')
            result.append(ch * count)
            digits = []

    if digits:
        raise ValueError('Invalid encoded string')

    return ''.join(result)

Time complexity: Compression: O(n), where n is the length of the input string. Decompression: O(m + k), where m is the encoded length and k is the decoded output length.. Space complexity: O(n) for compression output, and O(k) for decompression output..

Hints

1. For compression, scan left to right while tracking the current character and its run length.
2. For decompression, counts may have multiple digits, so collect consecutive digits before reading the following character.

Constraints

• mode is either 'pack' or 'unpack'.
• For packing, 0 <= len(data) <= 100000 and every value is in [0, 15].
• For unpacking, n is a non-negative integer and len(data) == ceil(n / 2).
• For unpacking, every packed byte is in [0, 255].
• Empty input is allowed.

Examples

Solution

def solution(mode, data, n=None):
    if mode == 'pack':
        packed = []
        i = 0
        while i < len(data):
            first = data[i]
            if not 0 <= first <= 15:
                raise ValueError('Values to pack must be in [0, 15]')

            second = 0
            if i + 1 < len(data):
                second = data[i + 1]
                if not 0 <= second <= 15:
                    raise ValueError('Values to pack must be in [0, 15]')

            packed.append((first << 4) | second)
            i += 2

        return packed

    if mode == 'unpack':
        if n is None or n < 0:
            raise ValueError('n must be a non-negative integer')
        if len(data) != (n + 1) // 2:
            raise ValueError('Packed data length does not match n')

        result = []
        for byte in data:
            if not 0 <= byte <= 255:
                raise ValueError('Packed bytes must be in [0, 255]')

            if len(result) < n:
                result.append((byte >> 4) & 0xF)
            if len(result) < n:
                result.append(byte & 0xF)

        return result

    raise ValueError("mode must be 'pack' or 'unpack'")

Time complexity: Packing: O(n). Unpacking: O(n), where n is the number of original integers.. Space complexity: Packing: O(ceil(n / 2)). Unpacking: O(n)..

Hints

1. To pack two 4-bit values a and b into one byte, put a in the high nibble using a << 4, then combine with b using bitwise OR.
2. To unpack a byte x, recover the first value with (x >> 4) & 15 and the second with x & 15. Stop once you have produced n values.