393. UTF-8 Validation

Problem Description

The challenge is to verify if an array of integers, data, consisting of the least significant 8 bits to represent a single byte, is a valid UTF-8 encoding sequence. UTF-8 encoding allows characters of lengths varying from 1 to 4 bytes, following specific patterns:

• A 1-byte character starts with a 0, followed by the actual code for the character.
• An n-bytes character sequence begins with n ones and a 0, followed by n-1 continuation bytes that each starts with 10.

The patterns for different byte lengths are as follows:

1. 1 byte: 0xxxxxxx
2. 2 bytes: 110xxxxx 10xxxxxx
3. 3 bytes: 1110xxxx 10xxxxxx 10xxxxxx
4. 4 bytes: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

This task is to assess each integer's binary representation in the input array to determine if it correctly represents a UTF-8 character as per the rules above.

Intuition

To resolve whether the data sequence is a valid UTF-8 encoding, one needs to examine each integer and identify the number of bytes the current character should have. This is done by checking the most significant bits (MSB) of each integer:

• If an integer starts with 0, it should be a single byte character.
• Otherwise, count the number of consecutive 1 bits at the start to know how many bytes the character should have. The count must be at least 2, and no more than 4, as UTF-8 can't have more than 4 byte characters.

If it's determined that a character is more than one byte long, the following integers should adhere to the 10xxxxxx pattern (where the MSB are 10), indicating that they are continuation bytes for the current character.

The solution iterates over each integer in the data array:

• If we're expecting continuation bytes (n > 0), check if the next byte follows the 10xxxxxx pattern. If not, return False.
• If it's the start of a sequence, based on the MSB pattern, determine the total number of bytes the character should consist of and expect that many continuation bytes to follow.
• At any point, if any byte does not meet the expected pattern, return False.

After checking all integers, we should not be expecting any more continuation bytes (n == 0). If we're still expecting bytes, then a complete character was not formed, and we also return False.

This assessment is repeated for each integer in the data array to confirm the entire sequence is valid UTF-8.

Solution Approach

The implementation of the solution revolves around bitwise operations, specifically right shifts >> and bitwise comparisons. There are no additional data structures required, as we can use scalar variables to track the state as we iterate through the data array.

Here's a step-by-step explanation of the algorithm used in the provided solution:

1. Initialize a counter n to zero. This counter will track the number of continuation bytes we expect to see for a character encoding.

2. Iterate through each integer v in the data list.

3. For each integer:

   • If we're expecting continuation bytes (n > 0):
     • Check if the integer is a continuation byte by right shifting 6 (v >> 6) and comparing if the result equals 0b10 (binary for 10xxxxxx). If it does not match, return False.
     • Decrement n by 1, because we have successfully found one of the expected continuation bytes.
   • If we're not expecting a continuation byte (n == 0), determine the number of bytes the UTF-8 character should have by checking the patterns:
     • If the integer starts with 0 (v >> 7 == 0), it's a 1-byte character, so we continue to the next integer.
     • If the integer starts with 110 (v >> 5 == 0b110), it's a 2-byte character. Set n to 1 since we expect one continuation byte.
     • If the integer starts with 1110 (v >> 4 == 0b1110), it's a 3-byte character. Set n to 2 since we expect two continuation bytes.
     • If the integer starts with 11110 (v >> 3 == 0b11110), it's a 4-byte character. Set n to 3 since we expect three continuation bytes.
     • If none of the above conditions are met, return False because the byte does not match any valid UTF-8 starting byte pattern.

4. After processing all integers, we check if n equals 0. If n is not 0, this implies that we were still expecting continuation bytes, and thus the sequence does not represent a properly terminated UTF-8 encoding, so we return False. If n is 0, every character has been processed correctly, and we return True.

The essence of the solution lies in the careful use of bitwise operations to examine the structure of each byte within an integer and validate that it conforms to the UTF-8 encoding rules.

Example Walkthrough

Let's go through a small example using the provided solution approach. Consider the array data with four integers, representing a possible UTF-8 encoded string:

1data = [197, 130, 1]

In binary, these integers are:

1197 -> 11000101
2130 -> 10000010
31   -> 00000001

Now, let's apply the solution approach to this example:

1. Initialize n to 0. This means we are not expecting any continuation bytes at the beginning.

2. Iterate through each integer in data:

3. Take the first integer 197 (11000101 in binary):

   • n == 0, so we're not expecting a continuation byte.
   • Right shift by 5 (197 >> 5), the result is 6 in decimal (110 in binary), matches the 110xxxxx pattern. This is the start of a 2-byte character, so we set n = 1 (expecting one continuation byte).

4. Move to the second integer 130 (10000010 in binary):

   • n > 0, so we are expecting a continuation byte.
   • Right shift by 6 (130 >> 6), the result is 2 in decimal (10 in binary), which matches the 10xxxxxx pattern for a continuation byte. This is correct. We decrement n by 1, making n = 0.

5. Move to the third integer 1 (00000001 in binary):

   • n == 0, so we are not expecting a continuation byte.
   • Right shift by 7 (1 >> 7), the result is 0 in decimal (0 in binary), which matches the pattern for a 1-byte character (0xxxxxxx).

6. Having processed all integers, we check if n equals 0 (which it does), indicating that we are not expecting any more continuation bytes and that the sequence represents a properly terminated UTF-8 encoding.

Therefore, according to the solution approach, the given data array [197, 130, 1] represents a valid UTF-8 encoded string.

Solution Implementation

Time and Space Complexity

The given Python code checks if a List of integers represent a valid sequence of UTF-8 encoded characters. It iterates once over all integers (bytes) in the input list to ensure they follow the UTF-8 encoding rules.

Time Complexity

The time complexity of the code is O(n), where n is the number of integers in the data list. This is because the code iterates over each integer exactly once. Each operation within the loop, such as bit shifting and comparison, is performed in constant time, so the time complexity is linear with respect to the input size.

Space Complexity

The space complexity of the solution is O(1), as the algorithm allocates a constant amount of space: a single counter n is used to keep track of the number of bytes that should follow the initial byte in a UTF-8 encoded character. No additional space that scales with the size of the input is used.

Learn more about how to find time and space complexity quickly using problem constraints.