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).