Leetcode – 1-bit and 2-bit Characters Solution in Python

In this comprehensive article, we will explore the Leetcode problem 717 – “1-bit and 2-bit Characters”. This problem revolves around the concept of binary decoding and tests the understanding of array manipulation.

Before we delve into solving this problem, let’s understand what it is asking us to do.

Problem Statement

The problem statement from Leetcode is as follows:

We have two special characters. The first character can be represented by one bit 0. The second character can be represented by two bits (10 or 11).

Now given a binary string represented by several bits. You need to determine whether the last character must be a one-bit character or not. The given string will always end with a zero.

Example 1:

Input: bits = [1, 0, 0]

Output: True

Explanation: The only way to decode it is two-bit character and one-bit character, so the last character is one-bit character.

Example 2:

Input: bits = [1, 1, 1, 0]

Output: False

Explanation: The only way to decode it is two-bit character and two-bit character, so the last character is NOT a one-bit character.

Approach 1: Iterative Solution

A straightforward way to solve this problem is to iterate through the array from the beginning. Whenever we encounter a 1, we know it’s the start of a two-bit character, so we skip the next bit. If the bit is 0, it’s a one-bit character, and we don’t skip any bit.

By the end of the loop, if we’re at the last index of the array, we know the last character is a one-bit character, so we return True. If we’ve gone past the last index, the last character was a two-bit character, and we return False.

Here is the Python code that implements this logic:

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        i = 0
        while i < len(bits) - 1:
            i += bits[i] + 1
        return i == len(bits) - 1

In this solution, the time complexity is O(n), where n is the length of the array. We are iterating through the array only once.

Approach 2: Greedy Solution

Another way to solve this problem is by using a greedy approach. We can observe that whenever we encounter a 1 in the array, the next bit is always part of the same character.

So we can scan the array from right to left. If we see a 1, we know that the current bit and the next bit on the left form a two-bit character, so we keep scanning to the left. If we see a 0, we know it’s a one-bit character, and we stop scanning.

If the first 0 we encounter is the last character of the array, we return True. Otherwise, we return False.

Here is the Python code that implements this logic:

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        parity = bits.pop()
        while bits and bits.pop(): 
            parity ^= 1
        return parity == 0

In this solution, the time complexity is O(n), where n is the number of 1s at the end of the array. In the worst-case scenario, this could be the entire array, so the time complexity is still O(n).

Approach 3: Optimal Solution

While the above solutions are correct, they are not the most efficient.

We can make use of a key observation – the given string will always end with a zero. Given this, we need to find out the number of continuous 1s just before the last 0. If this count is even, we can pair up the 1s and the last character must be a one-bit character. If the count is odd, the last character cannot be a one-bit character as one 1 will be left unpaired.

Here is the Python code that implements this logic:

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        count = 0
        i = len(bits) - 2
        while i >= 0 and bits[i] == 1:
            i -= 1
            count += 1
        return count % 2 == 0

This solution has a time complexity of O(n), where n is the number of 1s at the end of the array. However, it provides the best worst-case scenario among the three approaches, making it the most efficient solution.

Conclusion

This article delved into the problem of decoding 1-bit and 2-bit characters, a popular problem from Leetcode. It started by explaining the problem statement, followed by demonstrating three different approaches to solve the problem using Python.