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:


	For a 1-byte character, the first bit is a 0, followed by its Unicode code.
	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.

&nbsp;
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.


&nbsp;
Constraints:


	1 &lt;= data.length &lt;= 2 * 104
	0 &lt;= data[i] &lt;= 255


class Solution:
    def validUtf8(self, data: List[int]) -> bool:
        # Keep track of how many continuation bytes are left
		# Start at 0 since we are not expecting any continuation bytes at the beginning.
        cont_bytes_left = 0
        for byte in data:
            if cont_bytes_left == 0:
			    # If we don't expect any continuation bytes
			    # then there are 4 valid case for the current byte
                # byte >> 5 gives us the first 3 bits (8 bits - 5 = 3).
                if byte >> 5 == 0b110:
				    # After seeing a byte that starts with 110,
					# we expect to see one continuation byte
                    cont_bytes_left = 1
                elif byte >> 4 == 0b1110:
                    cont_bytes_left = 2
                elif byte >> 3 == 0b11110:
                    cont_bytes_left = 3
                # finally if the first bit isn't 0 then it's invalid
                elif byte >> 7 != 0:
                    return False
            else:
			    # If we are expecting a continuation byte there is only one valid case.
                # It's invalid if the continuation byte doesn't start with 10
                if byte >> 6 != 0b10:
                    return False
                cont_bytes_left -= 1
        
		# Only valid if we aren't expecting any more continuation bytes
        return cont_bytes_left == 0
class Solution {
    public boolean validUtf8(int[] data) {
        return help(data,0);
    }

    public boolean help(int[] data,int index) {
        int n=data.length-index;
        if(n==0){
            return true;
        }
        int c0=count(data[index]);
        if(c0<0||c0>n){
            return false;
        }
        for(int i=index+1;i<index+c0;i++){
            if((data[i]&0b10000000)!=0b10000000){
                return false;
            }
        }
        return help(data,index+c0);
    }

    private int count(int a){
        if((a>>3)==0b11110){
            return 4;
        }else if((a>>4)==0b1110){
            return 3;
        }else if((a>>5)==0b110){
            return 2;
        }else if((a>>7)==0){
            return 1;
        }
        return -1;
    }
}
class Solution{
public:
  bool validUtf8(vector<int> &data){
    int n = data.size(); 
    int count = 0;       
    for (int i = 0; i < n; i++){    
      int ele = data[i]; 
      if (!count){ 
	   // if the first 3 bits are 110, then the next byte is part of the current UTF-8 character
        if ((ele >> 5) == 0b110) 
          count = 1; 
		// if the first 4 bits are 1110, then the next 2 bytes are part of the current UTF-8 character  
        else if ((ele >> 4) == 0b1110)
          count = 2; 
		 // if the first 5 bits are 11110, then the next 3 bytes are part of the current UTF-8 character
        else if ((ele >> 3) == 0b11110)
          count = 3; 
		 // if the first bit is 1, then return false
        else if ((ele >> 7))
          return false; 
      }
      else{
	   // if the first 2 bits are not 10, then return false
        if ((ele >> 6) != 0b10)
          return false; 
        count--;        
      }
    }
    return (count == 0); 
  }
};
var validUtf8 = function(data) {
  const len = data.length;
  const byteBits = data.map(a => padLeft(a.toString(2))); //convert to bit strings
  let bytes,  i = 0;
  while (i < len) {
    bytes = 0;
    //count 1s in the front.
    while (byteBits[i].charAt(bytes) === "1") bytes++;

    //if we have only 1 byte to process expect more than 1 byte, it should fail.
    if (len === 1 && bytes > 0) return false;

    //UTF8 chars can't be more than 4 bytes.
    if (bytes > 4) return false;

    //if we're processing more than 1 byte
    if (bytes > 1) {
      //decrement for every byte that starts with "10"
      while (i < len - 1 && byteBits[++i].startsWith("10")) bytes--;

      //check to see if we have too many or too little of the expected bytes left
      if (bytes !== 1) return false;
    }
    else i++;
  }
  return true;
};

const padLeft = (str, size = 8, pad = "0") => (
  str.length >= size ? str : pad.repeat(size).substring(str.length % size) + str
);
UTF-8 Validation