DEV Community 👩‍💻👨‍💻

Cover image for #LeetCode 717. 1-bit and 2-bit Characters
Kunal Kamble
Kunal Kamble

Posted on

#LeetCode 717. 1-bit and 2-bit Characters

Problem Link: https://leetcode.com/problems/1-bit-and-2-bit-characters

Hi everyone
Kunal here with a new DSA blog. This is the 1st blog in the line of blogs. Here I have described how I solved a 717. 1-bit and 2-bit Characters. LeetCode question.

Requirement:

We have two three special characters:

  1. 1-bit: 00
  2. 2-bit: 1010 and 1111

From the given array of bits, we have to identify if the last character is part of a 1-bit character (i.e. only 00 ).

Test + Edge Cases:

  1. Input: bits = [1, 0, 0], Output: true
  2. Input: bits = [1, 1, 1, 0], Output: true
  3. Input: bits = [0, 0], Output: true There is no 0000 character so we need to choose 00 two times.

Solution:

Here we want to confirm that the last bit in the bits array can only be part of a 1-bit character. We should identify 2-bits and 1-bits characters in the array. As per requirements, if there is 11 present at any indexindex in the array then that indexindex and index+1index + 1 should be part of 2-bit characters. So now we have simple conditions that we can check against.

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        i = 0
        while i < len(bits):
            # If 1 is present then the next bit should be part of the 2-bit character
            # So skip the next bit
            if bits[i] == 1:
                i += 1

            # If at end of the list, 0 is present and not skipped 
            # Last bit should be a 1-bit character 
            elif bits[i] == 0 and i == len(bits) - 1:
                return True

            i += 1

        return False
Enter fullscreen mode Exit fullscreen mode

bits[i] == 0 is redundant here cause it should be covered as an else part of bits[i] == 1. Additionally, there is no point in checking i == len(bits) - 1 in every iteration, ideally we should verify if the current (not skipped) index points to the last index of bit at the end, outside of the loop.

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        i = 0
        n = len(bits)
        last = len(bits) - 1
        while i < last:
            # If 1 is present then the next bit should be part of the 2-bit character
            # So skip the next bit
            if bits[i] == 1:
                i += 1
            i += 1

        # If the last index is not skipped then it should be a 1-bit character
        return i == last
Enter fullscreen mode Exit fullscreen mode

Further optimization:

Let's focus on the last bit.

  1. Suppose there is one symbol / last bit then by definition it should be 00 and 1-bit.
  2. If the last bit and second last bit are 0000 then the last bit should be 1-bit as there is no 0000 character in 2-bit.
  3. If the last bit is followed up by one then the final result depends upon a number of the subsequent ones.
    1. If odd amount is present then the last bit cannot be a 1-bit character.
    2. If even amount is present then the last bit should be a 1-bit character
class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        n = len(bits)
        if n == 1:
            return True

        if bits[-2] == 0:
            return True

        ones = 0
        for i in range(n - 2, -1, -1):
            if bits[i] == 1:
                ones += 1
            else: break

        return ones % 2 == 0
Enter fullscreen mode Exit fullscreen mode

1st and second condition in the above code is redundant as in both of them a count of one is 0 which is even. So now we should just check if the count of ones is even or odd.

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        evenOnes = True
        for bit in bits[-2::-1]:
            if bit == 1:
                evenOnes = not evenOnes
            else: break

        return evenOnes
Enter fullscreen mode Exit fullscreen mode

Thanks for reading.

Top comments (0)

🌚 Friends don't let friends browse without dark mode.

Sorry, it's true.