Problem Brief

Find Number of Compatible Substrings

See Amazon online assessment and hiring insights

Amazon's product recommendation system aims to suggest relevant products to customers based on their recent purchase history. To achieve this, we need to identify substrings within a customer's purchase history that can be formed by concatenating all the available products in any order. We refer to such substrings as "compatible" substrings.

A substring of the purchase history is considered "compatible" if it can be formed by concatenating all the available products in any order, regardless of the order of concatenation.

Given n products, string history, and an array of string products, find the number of compatible substrings of history.

Note:

All the strings in products are of equal length.

Each available product must be concatenated exactly once in any order to check for compatibility.

The array products might contain duplicate products as well. In that case, each of the products (including duplicates) must be concatenated exactly once in any order as per the above rule.

Function Description

Complete the function findNumberOfCompatibleSubstrings in the editor.

findNumberOfCompatibleSubstrings has the following parameters:

String history: the purchase history
String[] products: an array of product strings

Returns

int: the number of compatible substrings

1Example 1

Input

history = "abcdefdefabcghidefabcxyz", products = ["abc", "def", "ghi"]

Output

Explanation

There are 3 substrings in history, that are compatible strings. The first substring "defabcghi", can be formed by concatenation of the available products in the following order [1, 0, 2] i.e.. by "def" + "abc" + "ghi" = "defabcghi". Hence, this substring is "compatible". The second substring "abcghidef", can be formed by concatenation of the available products in the following order [0, 2, 1] i.e.. by "abc" + "ghi" + "def" = "abcghidef". Hence, this substring is "compatible". The third substring "ghidefabc", can be formed by concatenation of the available products in the following order [2, 1, 0] i.e., by "ghi" + "def" + "abc" "ghidefabc". Hence, this substring is "compatible". No other substrings can be obtained by concatenating the products in any order. Hence, the answer is 3.