Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.
Example 1:
1 2 3 4 5 6 7 8
Input: s = "aaabb", k = 3
Output: 3
The longest substring is "aaa", as 'a' is repeated 3 times.
Example 2:
1 2 3 4 5 6 7
Input: s = "ababbc", k = 2
Output: 5
The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.
Given an encoded string, return it’s decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that kis guaranteed to be a positive integer.
You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.
Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or2[4].
Examples:
1 2 3
s = "3[a]2[bc]", return "aaabcbc". s = "3[a2[c]]", return "accaccacc". s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
stringdecodeStringImpl(int start, int end){ string ret; int index = start; while(index < end && !isDigit(s[index]) && s[index] != ']'){ index++; } ret += s.substr(start, index - start); while (index < end) { if(!isDigit(s[index])){ int j = index; while(j < end && !isDigit(s[j])) j++; ret += s.substr(index, j - index); index = j; } else{ int leftBracket = getInt(index); int repeat = stoi(s.substr(index, leftBracket - index)); int rightBracket = findRightBracket(leftBracket); string s = decodeStringImpl(leftBracket + 1, rightBracket); for (int i = 0; i < repeat; i++) { ret += s; } index = rightBracket + 1; } } return ret; }
intfindRightBracket(int index){ vector<int> st; st.push_back(index); int i = index; while (!st.empty() && i < s.length() - 1) { i++; if (s[i] == '[') st.push_back(i); elseif (s[i] == ']') st.pop_back(); } return i; }
Given an array of integers representing the data, return whether it is a valid utf-8 encoding.
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:
1 2 3 4 5
data = [197, 130, 1], which represents the octet sequence: 11000101 10000010 00000001.
Return true. It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.
Example 2:
1 2 3 4 5 6
data = [235, 140, 4], which represented the octet sequence: 11101011 10001100 00000100.
Return false. 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.