# FB week2

Given two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters 1 or 0.

Example 1:
Input: a = "11", b = "1"
Output: "100"

Example 2:
Input: a = "1010", b = "1011"
Output: "10101"

// 100
// 10101
// 11101
// carry = 0

public String addBinary(String a, String b) {
    StringBuilder sb = new StringBuilder();
    
    int lengthA = a.length() - 1;
    int lengthB = b.length() - 1;
    int carry = 0;
    
    while(lengthA >= 0 || lengthB >= 0) {
        int sum = carry;
        
        if (lengthA >= 0) {
            sum += a.charAt(lengthA) - '0';
            lengthA--;
        }
        
        if (lengthB >= 0) {
            sum += b.charAt(lengthB) - '0';;
            lengthB--;
        }  
        sb.append(sum / 2);
        carry = sum % 2;
    }
    
    if (carry > 0) {
        sb.append(carry);
    }
    
    return sb.reverse().toString();
    
}

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

[]
1,
1, 2,
1, 2, 3
1, 3
2
2, 3
3

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList();
    helper(nums, result, new ArrayList(), 0);
    return result;
}

// [1, 2, 3]
// [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]
        0      1      2       2
public void helper(int[] nums, List<List<Integer>> result, List<Integer> temp, int start) {
    result.add(new ArrayList(temp));
    for (int i = start; i < nums.length; i++) {
        temp.add(nums[i]); 
        helper(nums, result, temp, i+1);
        temp.remove(temp.size() - 1);
    }
}

In an alien language, surprisingly they also use english lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters.

Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographicaly in this alien language.

Example 1:
Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true
Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.

Example:
Input: words = ["ape","apple","bee","cat"], order = "abcdefghijklmnopqrstuvwxyz"
Output: true

Example:
Input: words = ["great","hey","cat","ufo"], order = "zyxwvutsrqponmlkjighfedcba"
Output: false

Example 2:
word
world
Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
Output: false
Explanation: As 'd' comes after 'l' in this language, then words[0] > words[1], hence the sequence is unsorted.

Example 3:
Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
Output: false
Explanation: The first three characters "app" match, and the second string is shorter (in size.) According to lexicographical rules "apple" > "app", because 'l' > '∅', where '∅' is defined as the blank character which is less than any other character (More info).

int[] mapping = new int[26];
    
public boolean isAlienSorted(String[] words, String order) {
    for (int i = 0; i < order.length(); i++) {
        mapping[order.charAt(i) - 'a'] = i;
    }
    for (int i = 1; i < words.length; i++) {
        if (compare(words[i - 1], words[i]) > 0) {
            return false;
        }
    }
    return true;
}

private int compare(String s1, String s2) {
    int n = s1.length();
    int m = s2.length();
    int cmp = 0;
    for (int i = 0, j = 0; i < n && j < m && cmp == 0; i++, j++) {
        cmp = mapping[s1.charAt(i) - 'a'] - mapping[s2.charAt(j) - 'a'];
    }
    return cmp == 0 ? n - m : cmp;
}

Input: words = ["world","word","row"], order = "worldabcefghijkmnpqstuvxyz"
[_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,0,_,_,_]

// hlabcdefgijkmnopqrstuvwxyz
[3,4,5,_,_,_,_,0,_,_,_,1,_,_,_,_,_,_,_,_,_,_]
[0, 1, 2, 3, 4, 5, 6]

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Example 1:
Input: "()())()"
Output: ["()()()", "(())()"]

Example 2:
Input: "(a)())()"
Output: ["(a)()()", "(a())()"]

Example 3:
Input: ")("
Output: [""]

public class Solution {
    public List<String> removeInvalidParentheses(String s) {
      List<String> res = new ArrayList<>();
      
      // sanity check
      if (s == null) return res;
      
      // "(a)())()"
      Set<String> visited = new HashSet<>();
      // "(a)())()"
      Queue<String> queue = new LinkedList<>();
      
      // initialize
      queue.add(s);
      visited.add(s);
      
      boolean found = false;
      
      while (!queue.isEmpty()) {
        s = queue.poll();
        
        if (isValid(s)) {
          // found an answer, add to the result
          res.add(s);
          found = true;
        }
      
        if (found) continue;
      
        // generate all possible states
        for (int i = 0; i < s.length(); i++) {
          // we only try to remove left or right paren
          if (s.charAt(i) != '(' && s.charAt(i) != ')') continue;
        
           // ")())()))))"
           // "(a)())()"
           // ")))))))((((("
           // (0, 5) -> (a)())
           // (5) -> ()
           // (a)()()
          String t = s.substring(0, i) + s.substring(i + 1);
        
          // visited = ["(a)())()","a)())()","(a())()","(a)))()","(a)()()"]
          // queue = ["(a)())()","a)())()","(a())()","(a)))()","(a)()()","(a)()()"]
          if (!visited.contains(t)) {
            // for each state, if it's not visited, add it to the queue
            queue.add(t);
            visited.add(t);
          }
        }
      }
      
      return res;
    }
    
    // "(a)())()"
    // "(a)"    
    // helper function checks if string s contains valid parantheses
    boolean isValid(String s) {
      int count = 0;
    
      for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(') count++;
        if (c == ')' && count-- == 0) return false;
      }
    
      return count == 0;
    }
    
    boolean isValid(String s) {
        int count = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') count++;
            if (c == ')') {
                if (count == 0) return false;
                count--;
            }
        }
        return count == 0;
    }
}

T(n) = n x C(n, n) + (n-1) x C(n, n-1) + ... + 1 x C(n, 1) = n x 2^(n-1).