Zenefits 一道面试题

一亩三分地上看的一道题.

给两个string,A和B

A = XYZ

A^2 = XXYYZZ

…..

B = XXadhflakjhelXXzzqqkkpoYYadadfhgakheZafhajkefhlZadhflkejhZfagjhfebhh

return k = 2, 因为b中有A^2的subsequence.

---

我用的run-length encode做的, 先找下a的count, 然后找下b的count, 这里的技巧是把在b但是不在a的字符存成负数. 这样encode的时候, 我们只encode a和b中共同的字符. 然后走一下数字的最小值就好了, 时间o(n).

package Interview;

/**
 * Created by chenguanghe on 9/2/15.
 */
    public class Zenefits {
    public int findK(String a, String b) {
        int[] count_a = new int[256];
        int[] count_b = new int[256];
        for (int i = 0; i < a.length(); i++) {
            count_a[a.charAt(i)]++;
        }
        for (int i = 0; i < b.length(); i++) {
            if (count_a[b.charAt(i)] == 0)
                count_b[b.charAt(i)] --;
            else
                count_b[b.charAt(i)] ++;
        }
        StringBuffer sb_b = new StringBuffer();
        for (int i = 0; i < b.length(); i++) {
            if (count_b[b.charAt(i)] > 0)
                sb_b.append(b.charAt(i));
        }
        String t_b = encode(sb_b.toString());
        int min = Integer.MAX_VALUE;
        for (int i = 0; i <t_b.length(); i++) {
            if (t_b.charAt(i) <= '9' && t_b.charAt(i) >= '0')
                min = Math.min(min, t_b.charAt(i) - '0');
        }
        return min;
    }
    public String encode(String s) {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            int counter = 1;
            while (i+1 < s.length() && s.charAt(i) == s.charAt(i+1)) {
                counter++;
                i++;
            }
            sb.append(counter);
            sb.append(s.charAt(i));
        }
        return sb.toString();
    }
    public static void main(String[] args) {
        String a = "XYX";
        String b = "XXadhflakjhelXXzzqqkkpoYadadfhgakheZafhajkefhlZadhflkejhZfagjhfebhhXX";
        System.out.println(new Zenefits().findK(a,b));
    }
    
}