Longest Subarray with Equal "1" and "0"

Problem: Given an array that only contains "1" and "0", find the longest subarray which contains equal number of "1" and "0".

Solution: With hash table, we can have a O(N) solution. The detail is as follow:

• First convert all "0" to "-1", then calculate c[i] = sum(a[0], ... , a[i]). It takes O(N) to calculate all the c[i].
• Then our task is to find a c[i] and a c[j] such that  c[i] = c[j]  and |j-i| is maximum. With a hash table, we can finish this job by doing a linear scan with a time complexity of   O(N).
• There is a special case you need to handle. When c[N-1] = 0 (assume N is the size of a), the longest subarray is just a itself.

The Longest Palindrome Substring (Manacher's algorithm)

Problem: Given a string, find a longest palindrome substring.

Solution: We can use general suffix tree that stores the original string and its reverse, which is an O(N) algorithm. However, here we give a better one with less space overhead while still O(N) complexity. This algorithm is called Manacher's algorithm. If we check a string from left to right, we can leverage the palindrome check we did previously. This is from the symmetry of palindrome. The main idea is as follow:

• Create an array called P[], P[i] stands for the longest palindrome centered at location i. Here i is not the index in the original string. For the original string, the locations we need to check for palindromes contains those characters in string along with the spaces between characters. So if we have a string of length l, we need to have a P[] with length 2*l+1.
• Our goal is to fill in P[]. For a particular position, we check its left and right. If equals, we extend our check further. Otherwise, the longest palindrome centered at location is found.
• However, we need to be smarter. Actually we can leverage previous computed P[i] when we calculate a P[x] where x>i. 
• So here we add two pointers, p1 and p2, which point to the left and right of the current location i such that |i-p1| = |i-p2| and p2>i>p1. We know p1 refers to a palindrome t and i refers to a palindrome s. If the first character of t is strictly on the right of the first character of s, we know P[p2] = P[p1].
• Otherwise, say if the first character of t is not strictly on the right of the first character of s, we have P[p2] >= r - p2. where r is the right bound of the palindrome that centered at i. We then need to check if the palindrome at p2 can be longer than r - p2. The good thing is that we only need to start the characters beyond the length of r - p2.
• When the first character of t is strictly on the right of the first character of s, we don't need to move the current center (i). Only when the first character of t is not strictly on the right of the first character of s, we need to move the current center to p2.
• The total cost is O(N).

The code is as follow:

void manacher(const string &s)
{
    int len = s.size();
    if(len == 0) return;

    int m[2*len+1];
    m[0] = 0;
    m[1] = 1;
    // "cur" is the current center
    // "r" is the right bound of the palindrome
    // that centered at current center
    int cur, r;
    r = 2;
    cur = 1;

    // iterate from 2 to 2*len+1
    for(int p2=2; p2<2*len+1; p2++)
    {
        int p1 = cur- (p2-cur);
        //if p1 is negative, we need to 
        //move "cur" forward

        // re-adjust cur based on p2
        while(p1 < 0)
        {
           cur++;
           r = m[cur] + cur;
           p1 = cur- (p2-cur);

        }

        // If the first character of t is 
        // strictly on the right of the 
        // first character of s

        //

        // Or here, from the symmetry, if

        // the palindrome centered at cur

        // cover the palindrome centered at

        // p1, we know
        if(m[p1] < r - p2)
            m[p2] = m[p1];
        //otherwise
        else
        {

           // we need to explore the length of

           // the palindrome centered at p2

           // if the palindrome centered at cur covers

           // p2, we can start at "k = r-p2"

           // otherwise, we start at "k=0"

           //reset "cur" 
           cur = p2;
           int k = r-p2;
           if(k<0) k = 0;
           while(1) 
           {
              if((p2+k+1)&1)
              {
                if(p2+k+1 < 2*len+1 && p2-k-1 >=0 && s[(p2+k)/2] == s[(p2-k-2)/2])
                  k++;
                else break;
              }
               else
              {
                if(p2+k+1 < 2*len+1 && p2-k-1 >=0)
                  k++;
                else break;
              }

           }
           // set the right boundary to be "p2+k"
           r = p2+k;
           m[p2] = k;
        }


    }

 
}

Find the Longest Sub-sequence that is a Palindrome within a String

Problem: Given a string, you can delete any characters, find the longest sub-sequence (the characters remained after your deletion) that is a palindrome.

Solution: For palindrome problem, one trick often used is to reverse the string. Here we first reverse the string, then find the longest common sub-sequence between the new string and the original one. It is a O(n^2) solution. Remember, there could be multiple longest common sub-sequences, some of them may not be palindrome, you need do some checks.

Paint a Cube with Three Colors

Problem: Given a cube, each face can be painted with one of the three colors. Calculate the ways the cube can be colored.

Solution: The problem can be solved by enumeration. While a more formal way is to use Burside's Lemma. Generally we need to understand the symmetry of the permutation on cubes. The main ideas of this method are listed as follows:

1. find the permutation groups of a cube, the easiest one is the identity permutation (just don't change). Then for the six faces, we have 1->1, 2->2 ... and 6->6. So for this permutation, there are 6 circles and the length of each circle is 1. Therefore we have a1^6, where a1 means the sub group that with circle length 1. "6" means there are 6 such circles.
2. then we can rotate along the axis that penetrates the centers of two opposite faces for 90 degree. If we do this, we have a1^2*a4, since two face unchanged, and the rest 4 form a circle. We have 6 such rotations. Therefore at the end we have 6*a1^2*a4.
3. then we can rotate along the axis that penetrates the centers of two opposite faces for 180 degree. If we do this, we have a1^2*a2^2.We have 3 such rotations. Therefore at the end we have 3*a1^2*a2^2.
4. then we can rotate the two opposite vertices (diagonal). We will have a3^2, since three faces that share one vertex are in one circle. We have 8 such rotations. Therefore at the end we have 8*a3^2.
5. then we can rotate along the axis that penetrates the middle points of two parallel edges that are not in the same face for 180 degree. We will have 6*a2^3 at the end.
6. so totally we have 1+6+3+8+6 = 24ways of permutations. So the cycle index (the ways to paint the cube) = 1/24*(a1^6+6*a1^2*a4+3*a1^2*a2^2+8*a3^2+6*a2^3). Since a1=a2=...=a6, we have cycle index =  1/24*(a^6+3*a^4+12*a^3+8*a^2). 
7. when a = 3, we have cycle index = 57.