# UTF-8 Validation **Difficulty:** MEDIUM [External](https://leetcode.com/problems/utf-8-validation) Canonical: https://scaleengineer.com/dsa/problems/utf-8-validation **Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation) **Data structures:** Array --- ## Problem Given an integer array `data` representing the data, return whether it is a valid **UTF-8** encoding (i.e. it translates to a sequence of valid UTF-8 encoded characters). A character in **UTF8** can be from **1 to 4 bytes** long, subjected to the following rules: 1. For a **1-byte** character, the first bit is a `0`, followed by its Unicode code. 2. For an **n-bytes** character, the first `n` bits are all one's, the `n + 1` bit is `0`, followed by `n - 1` bytes with the most significant `2` bits being `10`. This is how the UTF-8 encoding would work: Number of Bytes | UTF-8 Octet Sequence | (binary) --------------------+----------------------------------------- 1 | 0xxxxxxx 2 | 110xxxxx 10xxxxxx 3 | 1110xxxx 10xxxxxx 10xxxxxx 4 | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx `x` denotes a bit in the binary form of a byte that may be either `0` or `1`. **Note:** The input is an array of integers. Only the **least significant 8 bits** of each integer is used to store the data. This means each integer represents only 1 byte of data. **Example 1:** **Input:** data = [197,130,1] **Output:** true **Explanation:** data represents the octet sequence: 11000101 10000010 00000001. It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character. **Example 2:** **Input:** data = [235,140,4] **Output:** false **Explanation:** data represented the octet sequence: 11101011 10001100 00000100. The first 3 bits are all one's and the 4th bit is 0 means it is a 3-bytes character. The next byte is a continuation byte which starts with 10 and that's correct. But the second continuation byte does not start with 10, so it is invalid. **Constraints:** * `1 <= data.length <= 2 * 104` * `0 <= data[i] <= 255` # Approaches ## String Conversion and Prefix Matching This approach involves converting each integer in the input array into its 8-bit binary string representation. We then iterate through these binary strings, checking if they match the valid UTF-8 patterns. We'll need to maintain a counter to track the number of expected continuation bytes for multi-byte characters. **Time:** O(N) - We iterate through the N integers in the input array. For each integer, converting to a string and checking its prefix are constant time operations. · **Space:** O(1) - The space used for the binary string representation is constant (8 bits), and does not scale with the input size. **Pros:** Conceptually simple and easy to understand, as it directly mirrors the visual patterns of UTF-8 bytes.; Good for developers who are more comfortable with string operations than bitwise logic. **Cons:** Less performant than bit manipulation due to the overhead of creating and processing strings.; Requires a helper function to correctly format the binary string, adding slight complexity. ### Explanation We process the `data` array byte by byte. For each byte, we first convert it to an 8-bit binary string. A state variable, `continuationBytes`, keeps track of how many continuation bytes are expected. - If `continuationBytes` is 0, we are at the start of a new character. We check the prefix of the current binary string to determine the character's length: - Starts with `'0'`: 1-byte character. We continue. - Starts with `'110'`: 2-byte character. We set `continuationBytes` to 1. - Starts with `'1110'`: 3-byte character. We set `continuationBytes` to 2. - Starts with `'11110'`: 4-byte character. We set `continuationBytes` to 3. - Any other prefix (e.g., `'10'`, `'11111'`) is invalid, so we return `false`. - If `continuationBytes` is greater than 0, the current byte must be a continuation byte. - We check if its binary string starts with `'10'`. If yes, we decrement `continuationBytes`. If no, it's invalid. After checking all bytes, if `continuationBytes` is 0, the encoding is valid. Otherwise, it's invalid. ```java class Solution { public boolean validUtf8(int[] data) { int continuationBytes = 0; for (int num : data) { String binStr = toBinary(num); if (continuationBytes == 0) { if (binStr.startsWith("0")) { continuationBytes = 0; } else if (binStr.startsWith("110")) { continuationBytes = 1; } else if (binStr.startsWith("1110")) { continuationBytes = 2; } else if (binStr.startsWith("11110")) { continuationBytes = 3; } else { return false; } } else { if (binStr.startsWith("10")) { continuationBytes--; } else { return false; } } } return continuationBytes == 0; } private String toBinary(int num) { String bin = Integer.toBinaryString(num); while (bin.length() < 8) { bin = "0" + bin; } return bin; } } ``` ### Algorithm * Initialize a counter `continuationBytes` to 0. * Iterate through the `data` array from left to right. * For each integer `num`: * Convert `num` to its 8-bit binary string representation, padding with leading zeros if necessary. Let's call it `binStr`. * If `continuationBytes` is 0: * Check the prefix of `binStr`. * If it starts with `'0'`, it's a 1-byte character. Continue to the next integer. * If it starts with `'110'`, set `continuationBytes = 1`. * If it starts with `'1110'`, set `continuationBytes = 2`. * If it starts with `'11110'`, set `continuationBytes = 3`. * Otherwise, the sequence is invalid. Return `false`. * If `continuationBytes` > 0: * Check if `binStr` starts with `'10'`. * If it does, decrement `continuationBytes`. * If it doesn't, the sequence is invalid. Return `false`. * After the loop, if `continuationBytes` is 0, return `true`. Otherwise, it means the data ended with an incomplete character, so return `false`. ## State Machine with Bitwise Operations This is the most efficient approach. Instead of converting numbers to strings, we use bitwise operations to directly inspect the relevant bits of each integer. We process the data array as a state machine, where the state is the number of continuation bytes we expect to see. **Time:** O(N) - We perform a single pass over the input array of size N, with constant time operations for each element. · **Space:** O(1) - We only use a single integer variable to maintain the state, which is constant space. **Pros:** Optimal performance due to direct, low-level bitwise operations.; Concise and efficient implementation without the overhead of other data structures.; Uses constant extra space. **Cons:** Can be less intuitive for those not proficient with bitwise operations and hexadecimal/binary representations. ### Explanation We iterate through the `data` array, maintaining a state variable, `remainingBytes`, which counts the number of bytes remaining for the current multi-byte character. - When `remainingBytes` is 0, we are at the beginning of a new character. We examine the current byte (`num`) to determine its type and the number of bytes it spans using bitmasks and right shifts. - `(num >> 7) == 0b0`: 1-byte character. - `(num >> 5) == 0b110`: Start of a 2-byte character. We expect 1 continuation byte, so `remainingBytes = 1`. - `(num >> 4) == 0b1110`: Start of a 3-byte character. `remainingBytes = 2`. - `(num >> 3) == 0b11110`: Start of a 4-byte character. `remainingBytes = 3`. - If none of these patterns match, the byte is an invalid start for a character, and we return `false`. - When `remainingBytes` is greater than 0, the current byte must be a continuation byte, which must match the pattern `10xxxxxx`. We check this with `(num >> 6) == 0b10`. If it matches, we decrement `remainingBytes`. If not, the sequence is invalid. After iterating through the entire array, `remainingBytes` must be 0 for the encoding to be valid. ```java class Solution { public boolean validUtf8(int[] data) { int remainingBytes = 0; for (int num : data) { if (remainingBytes == 0) { // Start of a new character if ((num >> 7) == 0b0) { // 1-byte character: 0xxxxxxx remainingBytes = 0; } else if ((num >> 5) == 0b110) { // 2-byte character: 110xxxxx remainingBytes = 1; } else if ((num >> 4) == 0b1110) { // 3-byte character: 1110xxxx remainingBytes = 2; } else if ((num >> 3) == 0b11110) { // 4-byte character: 11110xxx remainingBytes = 3; } else { // Invalid starting byte return false; } } else { // Continuation byte if ((num >> 6) == 0b10) { // Must be 10xxxxxx remainingBytes--; } else { return false; } } } return remainingBytes == 0; } } ``` ### Algorithm * Initialize a counter `remainingBytes` to 0. * Iterate through each integer `num` in the `data` array. * If `remainingBytes` is 0: * This byte is the start of a new character. Determine its type using bitwise operations. * If `(num >> 7) == 0b0` (pattern `0xxxxxxx`), it's a 1-byte character. `remainingBytes` stays 0. * Else if `(num >> 5) == 0b110` (pattern `110xxxxx`), it's a 2-byte character. Set `remainingBytes = 1`. * Else if `(num >> 4) == 0b1110` (pattern `1110xxxx`), it's a 3-byte character. Set `remainingBytes = 2`. * Else if `(num >> 3) == 0b11110` (pattern `11110xxx`), it's a 4-byte character. Set `remainingBytes = 3`. * Otherwise, it's an invalid starting byte. Return `false`. * If `remainingBytes` > 0: * This byte must be a continuation byte. Check if it matches the pattern `10xxxxxx` using `(num >> 6) == 0b10`. * If it matches, decrement `remainingBytes`. * If it doesn't match, the sequence is invalid. Return `false`. * After the loop, if `remainingBytes` is 0, the entire sequence was valid. Return `true`. Otherwise, return `false`. # Solutions ### Java ```java class Solution { public boolean validUtf8(int[] data) { int n = 0; for (int v : data) { if (n > 0) { if (v >> 6 != 0b10) { return false; } --n; } else if (v >> 7 == 0) { n = 0; } else if (v >> 5 == 0b110) { n = 1; } else if (v >> 4 == 0b1110) { n = 2; } else if (v >> 3 == 0b11110) { n = 3; } else { return false; } } return n == 0; } } ``` ### CPP ```cpp class Solution { public: bool validUtf8(vector &data) { int n = 0; for (int &v : data) { if (n > 0) { if (v >> 6 != 0b10) return false; --n; } else if (v >> 7 == 0) n = 0; else if (v >> 5 == 0b110) n = 1; else if (v >> 4 == 0b1110) n = 2; else if (v >> 3 == 0b11110) n = 3; else return false; } return n == 0; } }; ``` ### Python ```python class Solution: def validUtf8(self, data: List[int]) -> bool: n = 0 for v in data: if n > 0: if v >> 6 != 0b10: return False n -= 1 elif v >> 7 == 0: n = 0 elif v >> 5 == 0b110: n = 1 elif v >> 4 == 0b1110: n = 2 elif v >> 3 == 0b11110: n = 3 else: return False return n == 0 ```