FastPrep
Problem · String

Find P-Matching Score

Learn this problem
● MediumAmazonOA
See Amazon hiring insights

Problem statement

Amazon has an extensive customer database. To prevent customers from having very similar usernames, Amazon's Customer Database Management Team has decided to define a "p-matching" score between two usernames.

Consider two users with their respective User IDs as userID1 of length n and userID2 of length m. Each User ID is represented as a string of lowercase English letters. The p-matching score of userID1 with respect to userID2 is the maximum number of distinct indices i such that the string formed by concatenating characters userID1[i], userID1[i + p]... userID1[i + (m - 1) x p] can be rearranged to userID2 where 0 ≤ i; i + (m - 1) x p ≤ n; 1 ≤ p.

Given two strings representing user IDs, find the p-matching between the given user IDs.

Function

findScore(userID1: String, userID2: String, p: int) → int

Complete the function findScore in the editor.

findScore has the following parameters:

  1. String userID1: the username of 1st user
  2. String userID2: the username of 2nd user
  3. int p: the interval at which the characters from userID1 are concatenated

Returns

int: the p-matching score of userID1 with respect to userID2.

Examples

Example 1

userID1 = "acaccaa"userID2 = "aac"p = 2return = 2

• Starting at index i = 0, increment i by p = 2, the string formed by concatenating characters userID1[0], userID1[2], userID1[4] is newString = "aca". It equals userID2 so i = 0 is a valid starting index.

• Starting at index i = 1, concatenate userID1[1], userID1[3], userID1[5] into newString = "cca". No rearrangement of this string will make it equal to string userID2 so i = 1 is not a valid starting index.

• Starting at index i = 2, concatenate userID1[2], userID1[4], userID1[6] into newString = "aca". It can be rearranged to "aac" so i = 2 is a valid starting index.

There are 2 valid starting indices, so the p-matching score is 2.

Constraints

  • 1 ≤ |userID2| ≤ |userID1| ≤ 105
  • 1 ≤ p ≤ 105
  • User strings userID1 and userID2 only contain lowercase Latin letters.

More Amazon problems

drafts saved locally
public int findScore(String userID1, String userID2, int p) {
    // write your code here
}
userID1"acaccaa"
userID2"aac"
p2
expected2
checking account