Efficient algorithm for finding subset with doubles and subset is together

Question

I have two arrays with letters. I want to know if array A is contained in array B as follows: The letters in A must appear adjacent to each other in array B but do not have to appear in the same order as they were in array A. Example that would be accepted

A = abcd B = hbadcg

A = aabc B = abcag

Examples that would not be accepted

A = aabcd B = adcbga

A = abcd B = abbcdg

What I could do is for every variation of A check if its a sub string in B. but I'm looking for a better way

Answer 1

Consider using a two-pointer approach for the given problem.

• Store the count of each character in A in a hash map - HashMapA
• Maintain two pointers, start and end as we iterate over the array B.
• Maintain yet another hash map to store the count of characters in the range [start, end] appearing in array B - HashMapB

Sharing ideone link for the same: https://ideone.com/vLmaxL

---

for(char c : A) HashMapA[c]++;

start = 0
for(int end = 0; end < B.length(); end++) {
  char c = B[end];
  HashMapB[c]++;
  while(HashMapB[c] > HashMapA[c] && start <= end) {
    HashMapB[ B[start] ]--;
    start++;  
  }
  if(end - start + 1 == A.length())
    return true;
} 

return false;