Sunday, April 5, 2015

LeetCode 159 Longest Substring with At Most Two Distinct Characters

problem

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.
For example, Given s = “eceba”,
T is "ece" which its length is 3.

Solution

The solution is simple, but has a little bit more cases.
We maintain 3 pointer, "first", "second" and a pointer point to current position. Using a hash map, the key of it is the letter, the value is the times of appearances. And a integer record current longest length.
When the current letter is not a new letter for the hash map, just + 1 on its value in hash map.
When the current letter is new to hash map, and the size of hash map is one, put this element into hash map and set its value to 1.
When the current letter is new to hash map but it already has two elements on it, we need to
  1. compute the length once (add all value of the element in hash map together) and may need to update the result,
  2. delete the element not on the current letter's left (the letter that the first pointer pointed to) from hash map. Thinking about the string "aaabbaacccc" when current pointer point to the first "c". We need to delete "b" from hash map.
  3. update the value of the element that second pointer pointed to to (current - second). In the example above, we need to set the value of "a" in hash map from 5 to 2
  4. add new element to hash map and set its value to 1.
At the end of every loop, current letter is not equal to its left letter, set first pointer to the position second pointer point to and set second point to current position.
After the loop, we need to do a extra compute to update the longest length.
The time complexity is O(n) for one pass of the string. Space complexity is O(1) because the hash map at most has two elements.
Here is code with some comment.
public int lengthOfLongestSubstringTwoDistinct(String s) {
    if (s == null || s.length() == 0) return 0;
    HashMap map = new HashMap<>(); // Character and number of its appearance
    int first = 0;
    int second = 0;
    int length = 0;
    map.put(s.charAt(0), 1);
    for (int i = 1; i < s.length(); i++) {
        
        // no new letter comes in, just update appearance times
        if (map.containsKey(s.charAt(i))) {
            map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
        }
        else {
            // new letter comes in, and just one letter in map
            // simply add the new letter and give value 1
            if (map.size() < 2) { 
                map.put(s.charAt(i), 1); // when less than two elements
            }
            else { 
                // third new element appeared
                // compute how many times the last two letters appeared. 
                int tmpLength = 0;
                for (char letter : map.keySet())
                    tmpLength += map.get(letter);
                length = Math.max(length, tmpLength);
                // delete letter not one the close left of current new letter
                map.remove(s.charAt(first));
                // update the value of the letter close to new letter. 
                map.put(s.charAt(second), i - second);
                // put new letter into map
                map.put(s.charAt(i), 1);
            }
        }
        if (s.charAt(i) != s.charAt(i-1)) {
            first = second;
            second = i;
        }
    }
    // the last two elements haven't count 
    int tmpLength = 0;
    for (char letter : map.keySet())
        tmpLength += map.get(letter);
    return Math.max(length, tmpLength);
}
Written with StackEdit.

Sunday, February 8, 2015

See My Name on neurolab's Contributor List

Last semester, I used neurolab to finish some of my Machine Learning assignments. In the process of using it, I find there are some incomplete and vague on the document. So I sent email to the author of that project and want to help him fix those problems.

The understanding of some function of neurolab is not an easy job because of the document. So after being authorized , I added some sentence to the function I have difficult to understand before.

Several weeks after I made change on document, the author sent me email said that he thanks my contribution and a new version released. Now, you can see my name on change log. This is the first time I actually contribute to a famous (at least to some degree) open source project. I feel good.

Written with StackEdit.

Monday, January 12, 2015

Need a summer internship!

In recent month, I've sent 15 or 20 resumes to different IT companies, but what I have now is only deny. I have to say that a student just learned one semester computer science is pretty hard to get an internship. But I don't just stay at home or library in my 3 months summer vocation or just get an unpaid internship that even impossible to cover foods and traffic cost. $1000 is enough for me.

The most important is to work in industry and know what the feel is when working in a company.

Written with StackEdit.

Friday, January 2, 2015

Binary Inorder Traversal Iterator

Problem

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.


For a binary search tree, kept returning the next smallest element is inorder traversal. Wikipedia has some great picture to show how to traversal in "preorder", "inorder" and "postorder". If you are not familiar with this, just go to Wikipedia.

The LeetCode always encourage us use loop other than recursion to solve tree traversal, because recursion may cost more extra space time for program stack and easy to understand.

When I see the problem, my first idea is push all the elements in the tree to a stack. But this cost O(n) memory. So a idea result is pop one from stack and push one to stack. Most method didn't do this precisely, just an amortized O(1) time and O(h) space. If the tree is pretty unbalanced, it is as same as push all the elements in stack. Here is code: private Stack nodes = new Stack<>();

public BSTIterator(TreeNode root) {
    pushToStack(root);
}

/** @return whether we have a next smallest number */
public boolean hasNext() {
    return !nodes.isEmpty();
}

/** @return the next smallest number */
public int next() {
    TreeNode tmp = nodes.pop();
    pushToStack(tmp.right);
    return tmp.val;
}

private void pushToStack(TreeNode node) {
    while (node != null) {
        nodes.push(node);
        node = node.left;
    }
}

The idea is keep going left until no more elements in left, than to right element and keep going left again. Redo above until no elements in the stack. The problems need to return elements inorder is the same idea. Binary Tree Inorder Tracersal could be solve use the same code structure:

public List<Integer> inorderTraversal(TreeNode root) {
    Stack<TreeNode> nodes = new Stack<>();
    ArrayList<Integer> result = new ArrayList<>();
    if (root == null)
        return result;

    pushToStack(root, nodes);

    while (!nodes.isEmpty()) {
        TreeNode tmp = nodes.pop();
        pushToStack(tmp.right, nodes);
        result.add(tmp.val);
    }
    return result;
}

public void pushToStack(TreeNode node, Stack<TreeNode> nodes) {
    while (node != null) {
        nodes.push(node);
        node = node.left;
    }
}

Written with StackEdit.