We have a two strings: A and B . We need to find minimum 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.
I think it can be solved like this:
Build a table of size [m][26]. table[i][j] stores the smallest position k >= i, where character j occurs. If there’s no such character, store -1. This can be build in O(m * alpha), where alpha = size of the alphabet, here 26.
Now you can just use a variable to keep track of the position in B which was last picked. Initially it will be 0. Say this variable is called p1.
Traverse through array A, finding table[p1][A[i]] each time.
If table[p1][A[i]] = -1, we have to add one more B. So ans++ and p1 = 0.
Else, p1 = table[p1][A[i]]+1;
ans will contain the number of copies of B needed. This will be O(n + m*alpha).
if character is not found i.e table[p1][A[i]] =-1, it means that character is not available in B so how answer is possible, as it is given that we can omit character in B not allowed to add character in B…
Correct me if i’m misunderstand ur method
Thanks
I think you misunderstood. table[p1][A[i]] = -1 means, after the index p1, there is no index in B where character A[i] exists. so for further matching, we need to take another B. for example, in B = “BAZ”, table[1][‘B’] will be -1 as after index 1, there is no index where ‘B’ is present. Hope this helps.
Thanks now i got it…