### imaking's blog

By imaking, history, 4 weeks ago, , We have a two strings: A and B. We need to find miniumum number of times that we could concatenate B to get A. Also we can omit any number of letters from B in any of the concatenations if we want. Example:

A = "ZAZA"
B = "BAZ"


A is obtained from 3 copies of B A= (--Z)(-AZ)(-A-)

Can you suggest any algorithmic approach which is better than O(nm) where n is length of A and m is length of B.  Comments (7)
 » 4 weeks ago, # | ← Rev. 4 →   O(n*26) solution exists where 26 = size of the alphabet
 » It's identical to this problen
 » First, concatenate B until it reaches the length of 2 * A. Then use a rolling hash to check the validity of each "starting point" and take the minimum of all valid positions. Total time is O(N).
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   ABC CBA How are 2 copies enough? I think you missed the "omit any letters" part.
•  » » » oops, you're right
 » One way would be to use a greedy approach letter for letter of A. Keep a pointer of where you currently are at string B. Then look for the first appearance of the current letter you're searching which is to the right of this pointer. When the pointer loops around B, that's one more concatenation you'll need. For example: Current letter in A | Pointer in B | Number of concatenations ----------------------------------------------------------------- - | 0 | 1 Z | 2 | 1 A | 1 | 2 Z | 2 | 2 A | 1 | 3 If you store the indexes where each letter appears in multiple sets, then you can find the next pointer in B with a lower_bound query, giving an O(n log m) time solution with O(m) memory. Another way would be to preprocess a table containing, for each letter and each index of B, where is its next appearance, giving an O(m * sigma) time for preprocessing (sigma being the size of the alphabet), O(n) time for solving and O(m * sigma) memory. This probably can be optimized further...
•  » » This is exactly how I have solved this question during my onsite interviewI was told it was optimal enough for the problem :DI was asked to create a function capable of saying if it was possible to reach string A from B, the follow up question was the minimum steps to reach that, like OP asked.