FastPrep
Problem · String

Find Number of Compatible Substrings

Learn this problem
● MediumAmazonOA
See Amazon hiring insights

Problem statement

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

    findNumberOfCompatibleSubstrings(history: String, products: String[]) → int

    Complete the function findNumberOfCompatibleSubstrings in the editor.

    findNumberOfCompatibleSubstrings has the following parameters:

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

    Returns

    int: the number of compatible substrings

    Examples

    Example 1

    history = "abcdefdefabcghidefabcxyz"products = ["abc", "def", "ghi"]return = 3
    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.

    More Amazon problems

    drafts saved locally
    public int findNumberOfCompatibleSubstrings(String history, String[] products) {
  // write your code here
}
    history"abcdefdefabcghidefabcxyz"
    products["abc", "def", "ghi"]
    expected3
    checking account