Google foobar challenge

Seawolf

一个比较有名的Google coding challenge，一共5个level，完成三个可以得到Google的interview，不是每个人都有机会，需要拿到link才可以参与，完成level 2 以后可以把link分享给他人。

level 1 -5 难度会逐渐增加，根据难度的不同每个题目都有不同的时间限制，代码可以用python 也可以用java，本人选择的是java，下面是一个level 1 的题目，due day 是 48 hours。

The cake is not a lie!
======================

Commander Lambda has had an incredibly successful week: she completed the first test run of her LAMBCHOP doomsday device, she captured six key members of the Bunny Rebellion, and she beat her personal high score in Tetris. To celebrate, she's ordered cake for everyone - even the lowliest of minions! But competition among minions is fierce, and if you don't cut exactly equal slices of cake for everyone, you'll get in big trouble. 

The cake is round, and decorated with M&Ms in a circle around the edge. But while the rest of the cake is uniform, the M&Ms are not: there are multiple colors, and every minion must get exactly the same sequence of M&Ms. Commander Lambda hates waste and will not tolerate any leftovers, so you also want to make sure you can serve the entire cake.

To help you best cut the cake, you have turned the sequence of colors of the M&Ms on the cake into a string: each possible letter (between a and z) corresponds to a unique color, and the sequence of M&Ms is given clockwise (the decorations form a circle around the outer edge of the cake).

Write a function called solution(s) that, given a non-empty string less than 200 characters in length describing the sequence of M&Ms, returns the maximum number of equal parts that can be cut from the cake without leaving any leftovers.

Languages
=========

To provide a Python solution, edit solution.py
To provide a Java solution, edit Solution.java

Test cases
==========
Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.

-- Python cases -- 
Input:
solution.solution("abcabcabcabc")
Output:
    4

Input:
solution.solution("abccbaabccba")
Output:
    2

-- Java cases -- 
Input:
Solution.solution("abcabcabcabc")
Output:
    4

Input:
Solution.solution("abccbaabccba")
Output:
    2

首次尝试，通过了7个case：

        
        public class Solution {
                
                public static int solution(String x) {
                        
                        int len = x.length();
                        
                        int count = 1;
                        
                        String a = "";
                        
                        String b = "";
                        
                        while(len >= 1) {
                                
                                a = x.substring(0, len/2);
                                
                                b = x.substring(len/2, len);
                                
                                if(a.equals(b)) {
                                        
                                        count = count * 2;
                                
                                }
                                        
                                len = len /2;
                        }
                        
                        return count;
                
                }
                
                public static void main(String[] args) {
                        
                        int c = solution("abccbaabccba");
                        
                        System.out.println(c);
                }
        }

但是这个代码有个问题，就是如果input全是相同的字母，则不能通过，于是稍作修改以后通过了8个case

        
        public class Solution {
                
                public static int solution(String x) {
                        
                        int len = x.length();
                        
                        int count = 1;
                        
                        int count1 = 0;
                        
                        String a = "";
                        
                        String b = "";
                        
                        for(int i = 0; i < len; i++) {
                                
                                if(x.substring(i, i+1).equals(x.substring(0, 1))){
                                        
                                        count1 ++;
                                }
                        }
                        
                        if(count1 == len) {
                                
                                return count1;
                        }
                        
                        while(len >= 1) {
                                
                                a = x.substring(0, len/2);
                                
                                b = x.substring(len/2, len);
                                
                                if(a.equals(b)) {
                                        
                                        count = count * 2;
                                
                                }
                                        
                                len = len /2;
                        }
                        
                        return count;
                
                }
                
                public static void main(String[] args) {
                        
                        int c = solution("abccbaabccba");
                        
                        System.out.println(c);
                }
        }

现在这个code 还有最后一个问题，就是当string的长度是奇数的时候无法通过，主要是设计思路还是有缺陷，于是打破之前的思路重新来写。

code:

public class Solution {
        
        public static int solution(String x) {
                
                int len = x.length();
                
                int ans = 0;
                
                for(int i = len; i >= 1; i --) {
                        
                        int n = len/i;
                        
                        if(len == n* i) {
                                
                                boolean t = true;
                                
                                String sub = x.substring(0, n);
                                
                                for(int j = 1; j <i; j++) {
                                        
                                        if(!x.substring(j*n, j*n + n).equals(sub)) {
                                                
                                                t= false;
                                                
                                                break;
                                                
                                        }
                                        
                                }
                                
                                if(t == true) {
                                        
                                        ans = i;
                                        
                                        break;
                                }
                        }
                        
                        
                }
        
        return ans;
        
        }
}

最终通过10个case，level 1 pass，记录一下。