3rd round 2

[KevinACoder]

""" 392. Is Subsequence (string) pass """ 
def isSubsequence(s, t : str) -> bool:
    i, j = 0, 0
    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            i += 1
        j += 1

    return i == len(s) #True if all characters in s have been found in t

[KevinACoder]

""" 393. UTF-8 Validation (bit manipulation) fail """
def validUtf8(data) -> bool:
    if len(data) == 0:
        return False

    first_bit_mask = 0b10000000 # 8 bit
    print(format(first_bit_mask, '02x'), first_bit_mask.bit_length())
    first_code = data[0]
    # count the first n bit as '1', which should be equal as
    #   the utf8 code length
    code_len = 1 
    while not (first_code&first_bit_mask) == 0:
        code_len += 1
        first_code = first_code<<1

    if code_len > 3:
        return False

    return code_len == len(data)

[KevinACoder]

""" 394. Decode String (string) fail"""
def findMatch(s: str, start: int): #-> int, int:
    left = 0
    beg, end = start, start
    # search for '[' and ']' from index start
    for i in range(start, len(s)):
        if s[i] == '[':
            # mark the beg of '[...]'
            left += 1
            if left == 1:
                beg = i
        elif s[i] == ']':
            left -= 1
            # mark the end of '[...]'
            if left == 0:
                end = i
                break

    # exception for logic error
    if left != 0:
        raise ValueError

    return beg, end

def decodeString(s : str) -> str:
    return decodeStringHelper(s, 1)

def decodeStringHelper(s : str, repeats : int) -> str:
    ans = ''
    # iterate over all characters
    for i in range(len(s)):
        if s[i].isdigit(): #if occur digit, recursivly do repeat
            beg, end = findMatch(s, i)
            ans += decodeStringHelper(s[beg:end], int(s[i:beg]) - 1)
            #print(s[i:beg])
            i = end + 1
        elif s[i] != '[' and s[i] != ']':
            ans += s[i]

    ans = ans*(repeats)
    return ans

[KevinACoder]

def decodeString2(s: str) -> str:
    idx = 0
    (ans, idx) = decodeStringHelper2(s, idx)
    return ans

def decodeStringHelper2(s: str, idx: int) -> (str, int):
    ans = ''
    # continue searching if reach end of string or ']'
    while idx < len(s) and s[idx] != ']':
        if s[idx].isdigit():
            repeats = 0
            # occur repeats num
            while idx < len(s) and s[idx].isdigit():
                repeats = repeats*10 + int(s[idx])
                idx += 1

            idx += 1 # skip '['
            # handle the string that needs to repeats
            (temp, idx) = decodeStringHelper2(s, idx)
            idx += 1 # skip ']'
            ans += temp*repeats
        else:
            ans += s[idx]
            idx += 1

    return (ans, idx)

[KevinACoder]

""" 395. Longest Substring with At Least K Repeating Characters (string, divide and conquer) fail"""
def longestSubstring2(s: str, k: int) -> int:
    # handling corner cases
    if len(s) < k:
        return 0
    elif k <= 1:
        return len(s)

    # search for longest valid substring
    return longestSubstringHelper2(s, 0, len(s)-1, k)

def longestSubstringHelper2(s: str, start, end, k: int) -> int:
    if end - start + 1 < k:
        return 0

    # cnt char frequencies of [start:end+1]
    tbl = {}
    for i in range(start, end + 1):
        if s[i] not in tbl:
            tbl[s[i]] = 1
        else:
            tbl[s[i]] += 1

    # split substring into [start:idx-1], [idx+1:end],
    #   find the first character (at idx) who has non-zero frequenies
    #   that small than k
    for key, val in tbl.items():
        if val > 0 and val < k:
            idx = s[start:end+1].find(key)
            # the character at idx must not exist in target sub string, otherwise
            #   there must exist an invalid character 
            return max(longestSubstringHelper2(s, start, idx-1, k),
            longestSubstringHelper2(s, idx+1, end, k))

    return end - start + 1

[KevinACoder]

""" 396. Rotate Function (simulation) fail"""
def maxRotateFunction(nums) -> int:
    max_val = 0
    size = len(nums)
    for i in range(size):
        nnums = nums[size-i-1:] + nums[:size-i-1]
        val = 0
        for j in range(size):
            val += nnums[j]*j
        max_val = max(max_val, val)
    return max_val

[KevinACoder]

""" 401. Binary Watch (backtrace, DFS)"""
import copy
def readBinaryWatch(num: int) -> list:
    bits = [0 for _ in range(10)]
    result, ans = [], []
    readBinaryWatchDFS(10, num, 0, bits, result)
    for r in result:
        hour_bits = r[:4]
        mins_bits = r[4:]
        hour, mins = 0, 0

        # calculate hour and mins
        for h in hour_bits:
            hour *= 2
            hour += h
        for m in mins_bits:
            mins *= 2
            mins += m

        # format string
        print(r)
        time = '' + str(hour) + ':'
        if mins < 10:
            time += '0' + str(mins)
        else:
            time += str(mins)
        ans.append(time)
    return ans 

def readBinaryWatchDFS(num, remain, idx: int, bits: list, result: list):
    if idx == num:
        if remain == 0:
            result.append(copy.deepcopy(bits)) #need to make a deep copy of bits
            #result.append(bits)
        return

    # try '0' and '1' at idx
    bits[idx] = 0
    readBinaryWatchDFS(num, remain, idx + 1, bits, result)
    if remain > 0: # reduce invalid branches
        bits[idx] = 1
        readBinaryWatchDFS(num, remain-1, idx + 1, bits, result)

[KevinACoder]

""" 402. Remove K Digits (stack, data structure)"""
def removeKdigits(num: str, k: int) -> str:
    """ 
    > 1, 4, 3, 2, 2, 1, 9
                            9
                    2   1   1
        4   3   2   2   2   2
    1   1   1   1   1   1   1  (remain num: 1219)
    """
    stack = []
    for s in num:
        i = int(s)
        # replace the stack top element if occur a smaller one
        #   stack contains all digit that will remain in the end
        while len(stack) > 0 and i < stack[-1] and k > 0:
            stack = stack[:-1]
            k -= 1
        stack.append(i)

    ans = ''
    for i in stack:
        ans += str(i)

    # left strip leading '0', if ans contains only '0', truncat to '0'
    if ans.count('0') != len(ans):
        ans = ans.lstrip('0')
    else:
        ans = ans[-1]

    return ans

[KevinACoder]

""" 404. Sum of Left Leaves """
from kit.binary_tree import TreeNode
def sumOfLeftLeaves(root: TreeNode) -> int:
    sums = 0
    sumOfLeftLeavesHelper(root, None, sums)
    return sums

def sumOfLeftLeavesHelper(root, parent: TreeNode, sum: int):
    if root == None:
        return

    if parent != None and root == parent.left and root.left == None and root.right == None:
        sum += root.val

    sumOfLeftLeavesHelper(root.left, root, sum)
    sumOfLeftLeavesHelper(root.right, root, sum)

[KevinACoder]

//405. Convert a Number to Hexadecimal
string toHex(int num) {
    if (num == 0) {
        return "0";
    }
    unsigned int n = static_cast<unsigned int>(num);
    string ans;

    while (n != 0) {
        unsigned int bit = n % 16;
        n /= 16;

        if (bit >= 10) {
            ans += 'a' + bit - 10;
        }
        else {
            ans += '0' + bit;
        }
    }

    reverse(ans.begin(), ans.end());
    return move(ans);
}

void ToHex() {
    cout << toHex(26) << " " << toHex(-1) << endl;
}

[KevinACoder]

//406. Queue Reconstruction by Height
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
    //sort the people queue by height increase order, if two person
    //  with identical height, person with less k put in behind
    sort(people.begin(), people.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
        return a.first > b.first || (a.first == b.first && a.second < b.second);
    });
    vector<pair<int, int>> ans;
    for (auto &p : people) {
        //put the person after k higher person
        ans.insert(ans.begin() + p.second, p);
    }
    return ans;
}

void ReconstructQueue() {
    auto que = reconstructQueue(vector<pair<int, int>>({ {7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2} }));
    for (auto & q : que) {
        cout <<"["<< q.first << " " << q.second << "]-";
    }
    cout << endl;
}

[KevinACoder]

//408. Valid Word Abbreviation (string)
//  wild card match (O(2n))
bool validWordAbbreviation(string word, string abbr) {
    string wildCard;
    int num = 0;
    //parse abbr into wild card
    for (auto & c : abbr) {
        if (isdigit(c)) {
            num *= 10;
            num += c - '0';
            if (num == 0) { return false; }
        }
        else {
            if (num > 0) {
                wildCard.append(num, '?');
                num = 0;
            }
            wildCard.append(1, c);
        }
    }

    if (num > 0) {
        wildCard.append(num, '?');
        num = 0;
    }

    //compare word with wild card char by char
    if (wildCard.size() != word.size()) { return false; }
    for (size_t i = 0; i < wildCard.size(); i++) {
        if (word.at(i) != wildCard.at(i) && wildCard.at(i) != '?') {
            return false;
        }
    }
    return true;
}

//in one loop
bool validWordAbbreviation2(const string &word, const string &abbr) {
    int skipNum = 0;
    size_t i = 0, j = 0;
    while (i < word.size() && j < abbr.size()) {
        if (isdigit(abbr.at(j))) {
            //accumlate the num of character need to skip in word
            skipNum = skipNum*10 + abbr.at(j) - '0';
            if (skipNum == 0) {
                return false;
            }
        }
        else {
            //skip num of chars and do check 
            i += skipNum;
            if (i >= word.size() || word.at(i) != abbr.at(j)) {
                return false;
            }
            skipNum = 0;
            i++;
        }
        j++;
    }

    i += skipNum;
    return i == word.size() && j == abbr.size();
}

void ValidWordAbbreviation() {
    cout << "ValidWordAbbreviation" << endl;
    cout << validWordAbbreviation("internationalization", "i12iz4n") << endl;
    cout << validWordAbbreviation("apple", "a2e") << endl;
    cout << validWordAbbreviation2("internationalization", "i12iz4n") << endl;
    cout << validWordAbbreviation2("apple", "a2e") << endl;
}

[KevinACoder]

//409. Longest Palindrome (string, hash table)
int longestPalindrome(string s) {
    unordered_map<char, int> freq;
    for (auto & c : s) {
        freq[c]++;
    }

    int hasCenter = 0;
    int ans = 0;
    for (auto & f : freq) {
        if (f.second % 2 == 1) {
            //grab one odd as center, put the rest in palindrome
            hasCenter = 1;
            ans += f.second - 1;
        }
        else {
            //all even part can be put in palindrome
            ans += f.second;
        }
    }

    return ans + hasCenter;
}

void LongestPalindrome() {
    cout << "LongestPalindrome" << endl;
    cout << longestPalindrome("abccccdd") << endl;
}

[KevinACoder]

//412. Fizz Buzz (math)
vector<string> fizzBuzz(int n) {
    vector<string> ans;
    if (n < 0) {
        return ans;
    }

    for (int i = 1; i <= n; i++) {
        string token;
        if (i % 3 != 0 && i % 5 != 0) {
            token.append(to_string(i));
        }
        else {
            if (i % 3 == 0) {
                token += "Fizz";
            }

            if (i % 5 == 0) {
                token += "Buzz";
            }
        }
        ans.push_back(token);
    }

    return move(ans);
}

void FizzBuzz() {
    cout << "FizzBuzz" << endl;
    Print(fizzBuzz(15));
}

[KevinACoder]

//413. Arithmetic Slices (DP)
int numberOfArithmeticSlices(vector<int>& nums) {
    size_t N = nums.size();
    vector<int> dp(N, 0); //num of slice end at i
    int ans = 0;
    for (size_t i = 2; i < N; i++) {
        // one more slice satified
        if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
            dp[i] = dp[i - 1] + 1;
        }
        ans += dp[i];
    }

    return ans;
}

void NumberOfArithmeticSlices() {
    cout << "NumberOfArithmeticSlices" << endl;
    cout << numberOfArithmeticSlices(vector<int>{1, 2, 3, 4}) << endl;
}

[KevinACoder]

//414. Third Maximum Number (data structure app)
int thirdMax(vector<int>& nums) {
    set<int> que;
    //build a set with length at most 3
    for (auto & ele : nums) {
        que.insert(ele);
        if (que.size() > 3) {
            que.erase(que.begin());
        }
    }

    //if the third max num does not exist, return the maximum one
    return que.size() >= 3 ? *que.begin() : *que.rbegin();
}

void ThirdMax() {
    cout << "ThirdMax" << endl;
    cout << (thirdMax(vector<int>{3, 2, 1}) == 1) << endl;
    cout << (thirdMax(vector<int>{1, 2}) == 2) << endl;
    cout << (thirdMax(vector<int>{2, 2, 3, 1}) == 1) << endl;

[KevinACoder]

//415. Add Strings (string)
string addStrings(string num1, string num2) {
    string ans;
    reverse(num1.begin(), num1.end());
    reverse(num2.begin(), num2.end());
    int carry = 0, ele1 = 0, ele2 = 0;
    auto it1 = num1.cbegin(), it2 = num2.cbegin();
    while (it1 != num1.cend() && it2 != num2.cend()) {
        ele1 = it1 != num1.cend() ? *it1 - '0' : 0;
        ele2 = it2 != num2.cend() ? *it2 - '0' : 0;
        ans.append(to_string((ele1 + ele2 + carry) % 10));
        carry = (ele1 + ele2 + carry) / 10;
        it1++;
        it2++;
    }

    if (carry > 0) {
        ans.append(to_string(carry));
    }

    reverse(ans.begin(), ans.end());
    return move(ans);
}

void AddStrings() {
    cout << "AddStrings" << endl;
    cout << addStrings("1984", "9315") << endl;
}

[KevinACoder]

//416. Partition Equal Subset Sum (DP)
bool canPartition(vector<int> &nums) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    int target = sum >> 1; //sum/2
    if (sum & 0x01) { //it is impossible to partition odd sum array
        return false;
    }

    //dp[i] = true means there exist a subset sum to i
    vector<bool> dp(target + 1, true); 
    for (auto const & ele : nums) {
        for (int i = target; i >= ele; i--) {
            //if i - ele is a possible subet sum, join
            //  ele makes new subset sum i
            dp[i] = dp[i] || dp[i - ele];
        }
    }

    return dp[target];
}

void CanPartition() {
    cout << "CanPartition" << endl;
    cout << canPartition(vector<int>{1, 5, 11, 5}) << endl;
    cout << canPartition(vector<int>{1, 2, 3, 5}) << endl;
}

[KevinACoder]

//418. Sentence Screen Fitting (Simulation)
int wordsTyping(vector<string>& sentence, int rows, int cols) {
    //i, j (ptr), k (idx of word)
    int i = 0, j = 0, k = 0;
    int N = static_cast<int>(sentence.size());
    string str;
    if (N <= 0) {
        return 0;
    }

    //loop until i, j reach the end of screen
    while (i < rows) {
        if (j < cols && static_cast<int>(sentence[k%N].size()) <= cols - j) {
            j += sentence[k%N].size() + 1; //add one space after the word
            str += sentence[k%N] + " ";
            k++; //check for the next word
        }
        else {
            str += "\n";
            i++; //new line
            j = 0;
        }
    }

    //k / sentence.size() is the ans
    //cout << str << endl; //for debug
    return k / N;
}

void WordsTyping() {
    cout << "WordsTyping"<< endl;
    cout << (wordsTyping(vector<string>{"hello", "world"}, 2, 8) == 1) << endl;
    cout << (wordsTyping(vector<string>{"a", "bcd", "e"}, 3, 6) == 2) << endl;
    cout << (wordsTyping(vector<string>{"I", "had", "apple", "pie"}, 4, 5) == 1) << endl;
}

[KevinACoder]

//422. Valid Word Square
bool validWordSquare(vector<string>& words) {
    for (size_t i = 0; i < words.size(); i++) {
        for (size_t j = 0; j < words[i].size(); j++) {
            if (words.size() != words[i].size() || words[i][j] != words[j][i]) {
                return false;
            }
        }
    }
    return true;
}