largest K such that A^K is a subsequence of B - Zenefits

http://www.1point3acres.com/bbs/thread-145290-1-1.html
// Find the largest K such that A^K is a subsequence of B, where A, B are two strings. |A| << |B|.

// Power of a string:
// Let A = xyxz 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�. 
// Then,
// A^1 = A = xyxz
// A^2 = xxyyxxzz
// A^3 = xxxyyyxxxzzz
. 1point 3acres 璁哄潧
// Example:-google 1point3acres
// A = xyxz
// B = xabyzxz

// B xaybyxzxxxzz

// A xxyyxxzz

http://buttercola.blogspot.com/2015/12/zenefits-largest-subsequence.html

The key of the problem is to find out the largest possible k, that the A^k is the subsequence of B. 

How to find out the maximum K. The easiest way is k = lenB / lenA. But that could result to a false larger K. 

A better approach is to calculate the frequency of each character in A and B. Then calculate the MIN(B[i] / A[i]).

    public int findK(String A, String B) {

        int len1 = A.length(), len2 = B.length();

        if (len1 > len2) {

            return 0;

        }

         

        if (len1 <= 0) {

          return 0;

        }

         

        // remove space weird characters, capital to lower case etc if needed

        A = preprocess(A);

             

        // find signature for each A and B and get the max possible value for k

        int[] sigA = new int[256];

        int[] sigB = new int[256];

        for (int i = 0; i < len1; i++) {

            sigA[A.charAt(i)]++;

        }

        for (int i = 0; i < len2; i++) {

            sigB[B.charAt(i)]++;

        }

         

        int kMax = Integer.MAX_VALUE;

        for (int i = 0; i < len1; i++) {

            if (sigA[A.charAt(i)] != 0) {

                kMax = Math.min(sigB[A.charAt(i)] / sigA[A.charAt(i)], kMax);

            }

        }

         

        int lo = 0, hi = kMax;

        int ret = 0;

        while (lo <= hi) {

            int med = lo + (hi - lo) / 2;

            if (isSubSeq(expand(A, med), B)){

                ret = med;

                lo = med + 1;

            } else {

                hi = med - 1;

            }

        }

        return ret;

    }

   

    String expand(String A, int k){

        StringBuilder sbuf = new StringBuilder();

        for (int i = 0; i < A.length(); i++) {

            char c = A.charAt(i);

            for (int j = 0; j < k; j++) {

                sbuf.append(c);

            }

        }

        return sbuf.toString();

    }

         

    boolean isSubSeq(String A, String B) {

        int len1 = A.length(), len2 = B.length();

        int a = 0, b = 0;

        while (a < len1 && b < len2){

            if (A.charAt(a) == B.charAt(b)){

                a++;

                b++;

            } else {

                b++;

            }

        }

        return a == len1;

    }

         

    String preprocess(String A){

        return A.toLowerCase();

    }

1. public int findK(String A, String B){
2.             int len1 = A.length(), len2 = B.length();
3.             if (len1 > len2) return 0;
4.             if (len1 <= 0) return 0;
5.             // remove space weird characters, capital to lower case etc if needed.
6.             A = preprocess(A);
7.             // find signature for each A and B and get the max possible value for k. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
8.             int[] sigA = new int[256];
9.             int[] sigB = new int[256];. Waral 鍗氬鏈夋洿澶氭枃绔�,
10.             for (int i = 0; i < len1; i++) sigA[A.charAt(i)]++;
11.             for (int i = 0; i < len2; i++) sigB[B.charAt(i)]++;
12.             int kMax = Integer.MAX_VALUE;. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
13.             for (int i = 0; i < len1; i++){
14.                 if (sigA[A.charAt(i)] != 0) kMax = Math.min(sigB[A.charAt(i)] / sigA[A.charAt(i)], kMax);
15.             }
16.             int lo = 0, hi = kMax;. 鍥磋鎴戜滑@1point 3 acres
17.             int ret = 0;
18.             while (lo <= hi){
19.                 int med = lo + (hi - lo) / 2;
20.                 if (isSubSeq(expand(A, med), B)){
21.                     ret = med;
22.                     lo = med + 1; 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�. 
23.                 } else {
24.                     hi = med - 1;
25.                 }
26.             }
27.             return ret;
28.         }
29.         
30.         String expand(String A, int k){
31.             StringBuilder sbuf = new StringBuilder();
32.             for (int i = 0; i < A.length(); i++){
33.                 char c = A.charAt(i);
34.                 for (int j = 0; j < k; j++) sbuf.append(c);
35.             }. more info on 1point3acres.com
36.             return sbuf.toString();
37.         }
38.         
39.         boolean isSubSeq(String A, String B){
40.             int len1 = A.length(), len2 = B.length();
41.             int a = 0, b = 0;
42.             while (a < len1 && b < len2){
43.                 if (A.charAt(a) == B.charAt(b)){
44.                     a++;
45.                     b++;
46.                 } else {
47.                     b++;. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
48.                 }
49.             }
50.             return a == len1;. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
51.         }
52.         
53.         String preprocess(String A){
54.             return A.toLowerCase();
55.         }

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=143470&highlight=zenefit
一开始思路就是k从1一个个试，不行就返回。找subsequence用dp。但是面试官说复杂度太高，就想到用双指针遍历。然后问了时间复杂度。 写好后他还要improve.想到用二分查找k.因为最小是1，最大是B.length()/A.length();

subsequence是不需要连续的。如果x^(K+1)是y的subsequence，x^(K)一定是y的subsequence

1.         public int findLargestK(String s1, String s2){.鏈枃鍘熷垱鑷�1point3acres璁哄潧
2.                 if(s1.length() < 1 || s1.length() > s2.length())
3.                         return -1;
4.                 int k = 1;
5.                 int left = 1, right = s2.length() / s1.length();
6.                 int lastK = -1;
7.                 while(left <= right){
8.                         k = left + (right - left)/2;
9.                         String akString = generateKth(s1, k);
10.                         if(isSub(akString, s2)){
11.                                 lastK = k;
12.                                 left = k + 1;
13.                         }else{. visit 1point3acres.com for more.
14.                                 right = k - 1;
15.                         }
16.                 }
17.                 return lastK;
18.         }
19.         
20.         private String generateKth(String s, int k){
21.                 StringBuilder temp = new StringBuilder();
22.                 for(int i = 0; i < s.length(); i++){
23.                         for(int j = 0; j < k; j++){. Waral 鍗氬鏈夋洿澶氭枃绔�,
24.                                 temp.append(s.charAt(i));
25.                         }
26.                 }
27.                 return temp.toString();
28.         }. more info on 1point3acres.com
29.         
30.         private boolean isSub(String s1, String s2){
31.                 int i = 0;
32.                 int j = 0;
33.                 while(i < s1.length() && j < s2.length()){
34.                         if(s1.charAt(i) == s2.charAt(j)){. 1point 3acres 璁哄潧
35.                                 i++;
36.                         }
37.                         j++;-google 1point3acres
38.                 }
39.                 if(i == s1.length())
40.                         return true;
41.                 return false;
42.         }