FastPrep
Problem · String

Find P-Matching Score

Learn this problem
● MediumAmazonNEW GRADOA
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