UTF-8 Validation
UTF-8 Validation is a medium bit manipulation problem solved with the basics pattern.
The best approach, optimal (bit masks with a pending counter), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (binary strings) up.
Problem
You are given an array data where each integer is one byte (only its lowest 8 bits matter). Decide whether the bytes form a valid UTF-8 encoding.
A character is 1 to 4 bytes long:
- 1 byte:
0xxxxxxx - 2 bytes:
110xxxxx 10xxxxxx - 3 bytes:
1110xxxx 10xxxxxx 10xxxxxx - 4 bytes:
11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
Every byte after the first one of a character must start with 10. Return true if the whole array splits into valid characters, otherwise false.
Examples
Example 1
- Input
data = [65, 194, 169]- Output
true- Why
- 65 = 01000001 is a 1-byte character. 194 = 11000010 starts a 2-byte character and 169 = 10101001 is its continuation byte.
Example 2
- Input
data = [240, 162, 138]- Output
false- Why
- 240 = 11110000 announces a 4-byte character, but only two continuation bytes follow.
Example 3
- Input
data = [145]- Output
false- Why
- 145 = 10010001 is a continuation byte with no character before it.
Constraints
1 <= data.length <= 2 * 10^40 <= data[i] <= 255
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 17 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (binary strings) | O(n) | O(1) |
| Optimal (bit masks with a pending counter) | O(n) | O(1) |
1Brute force (binary strings)
O(n)Every byte is turned into a string of fixed length 8 and checked once, but with a large constant factor.O(1)Only one 8-character string at a time.Write each byte as an 8-character binary string and count its leading '1' characters. Use that count to decide how many continuation bytes must follow, then check that each of those strings starts with "10".
- For index i, build the 8-bit string of data[i] and count leading '1's as k.
- k == 0: move to i + 1. k == 1 or k > 4: return false.
- Otherwise the next k - 1 bytes must exist and each string must start with "10"; then move to i + k.
- Return true when all bytes are consumed.
class Solution {
public boolean validUtf8(int[] data) {
int i = 0, n = data.length;
while (i < n) {
String bits = toBits(data[i]);
int k = 0;
while (k < 8 && bits.charAt(k) == '1') k++;
if (k == 0) { i++; continue; }
if (k == 1 || k > 4 || i + k > n) return false;
for (int j = i + 1; j < i + k; j++) {
if (!toBits(data[j]).startsWith("10")) return false;
}
i += k;
}
return true;
}
private String toBits(int b) {
String s = Integer.toBinaryString(b & 0xFF);
while (s.length() < 8) s = "0" + s;
return s;
}
}class Solution:
def validUtf8(self, data: List[int]) -> bool:
i, n = 0, len(data)
while i < n:
bits = format(data[i] & 0xFF, "08b")
k = len(bits) - len(bits.lstrip("1"))
if k == 0:
i += 1
continue
if k == 1 or k > 4 or i + k > n:
return False
for j in range(i + 1, i + k):
if not format(data[j] & 0xFF, "08b").startswith("10"):
return False
i += k
return Trueclass Solution {
string toBits(int b) {
return bitset<8>(b & 0xFF).to_string();
}
public:
bool validUtf8(vector<int>& data) {
int i = 0, n = data.size();
while (i < n) {
string bits = toBits(data[i]);
int k = 0;
while (k < 8 && bits[k] == '1') k++;
if (k == 0) { i++; continue; }
if (k == 1 || k > 4 || i + k > n) return false;
for (int j = i + 1; j < i + k; j++) {
if (toBits(data[j]).substr(0, 2) != "10") return false;
}
i += k;
}
return true;
}
};function validUtf8(data) {
const toBits = (b) => (b & 0xff).toString(2).padStart(8, "0");
let i = 0;
const n = data.length;
while (i < n) {
const bits = toBits(data[i]);
let k = 0;
while (k < 8 && bits[k] === "1") k++;
if (k === 0) { i++; continue; }
if (k === 1 || k > 4 || i + k > n) return false;
for (let j = i + 1; j < i + k; j++) {
if (!toBits(data[j]).startsWith("10")) return false;
}
i += k;
}
return true;
}2Optimal (bit masks with a pending counter)
O(n)One pass with a few bit operations per byte.O(1)Only the counter.Walk the bytes once, keeping need, the number of continuation bytes still expected. When need is 0, the byte is a header: classify it with masks. When need > 0, the byte must match 10xxxxxx. At the end nothing may still be pending.
- If need > 0: if (b & 0xC0) != 0x80 return false; else need--.
- Otherwise: (b & 0x80) == 0 means need = 0; (b & 0xE0) == 0xC0 means need = 1; (b & 0xF0) == 0xE0 means need = 2; (b & 0xF8) == 0xF0 means need = 3; anything else is invalid.
- Return need == 0 after the loop.
class Solution {
public boolean validUtf8(int[] data) {
int need = 0;
for (int x : data) {
int b = x & 0xFF;
if (need > 0) {
if ((b & 0xC0) != 0x80) return false;
need--;
} else if ((b & 0x80) == 0) {
need = 0;
} else if ((b & 0xE0) == 0xC0) {
need = 1;
} else if ((b & 0xF0) == 0xE0) {
need = 2;
} else if ((b & 0xF8) == 0xF0) {
need = 3;
} else {
return false;
}
}
return need == 0;
}
}class Solution:
def validUtf8(self, data: List[int]) -> bool:
need = 0
for x in data:
b = x & 0xFF
if need > 0:
if (b & 0xC0) != 0x80:
return False
need -= 1
elif (b & 0x80) == 0:
need = 0
elif (b & 0xE0) == 0xC0:
need = 1
elif (b & 0xF0) == 0xE0:
need = 2
elif (b & 0xF8) == 0xF0:
need = 3
else:
return False
return need == 0class Solution {
public:
bool validUtf8(vector<int>& data) {
int need = 0;
for (int x : data) {
int b = x & 0xFF;
if (need > 0) {
if ((b & 0xC0) != 0x80) return false;
need--;
} else if ((b & 0x80) == 0) {
need = 0;
} else if ((b & 0xE0) == 0xC0) {
need = 1;
} else if ((b & 0xF0) == 0xE0) {
need = 2;
} else if ((b & 0xF8) == 0xF0) {
need = 3;
} else {
return false;
}
}
return need == 0;
}
};function validUtf8(data) {
let need = 0;
for (const x of data) {
const b = x & 0xff;
if (need > 0) {
if ((b & 0xc0) !== 0x80) return false;
need--;
} else if ((b & 0x80) === 0) {
need = 0;
} else if ((b & 0xe0) === 0xc0) {
need = 1;
} else if ((b & 0xf0) === 0xe0) {
need = 2;
} else if ((b & 0xf8) === 0xf0) {
need = 3;
} else {
return false;
}
}
return need === 0;
}Edge cases to test
- A lone continuation byte (starts with 10)
- A header byte with five or more leading 1s (like 11111000)
- The data ends in the middle of a multi-byte character
- All ASCII bytes (every byte below 128)
Hints
Hint 1
Count the leading 1 bits of a byte: 0 means a 1-byte character, 2 to 4 mean a character of that many bytes, 1 or more than 4 is invalid as a first byte.
Hint 2
Keep a counter of how many continuation bytes are still expected; each of them must look like 10xxxxxx.
Hint 3
Masks do the checks without strings: (b & 0b11000000) == 0b10000000 tests for a continuation byte.
FAQ
What is the best time complexity for UTF-8 Validation?
Optimal (bit masks with a pending counter) runs in O(n) time and O(1) extra space. One pass with a few bit operations per byte.
Which pattern does UTF-8 Validation use?
It is a bit manipulation problem that uses the basics pattern. Other problems with the same pattern: Decimal to binary, Convert Binary Number in a Linked List to Integer, K-th Bit is Set or Not.
Is there a brute force solution for UTF-8 Validation?
Yes. Brute force (binary strings) takes O(n) time and O(1) space. Write each byte as an 8-character binary string and count its leading '1' characters.
Which edge cases should I test for UTF-8 Validation?
A lone continuation byte (starts with 10); A header byte with five or more leading 1s (like 11111000); The data ends in the middle of a multi-byte character; All ASCII bytes (every byte below 128).