## Saturday, November 28, 2015

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

// 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 璁哄潧
// A = xyxz
// B = xabyzxz

// B xaybyxzxxxzz

// A xxyyxxzz
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);
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.         }

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();
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.                         }
38.                 }
39.                 if(i == s1.length())
40.                         return true;
41.                 return false;
42.         }