Amazon OA | SDE-1 (1+ YOE) | India

Round 1

Questions: 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)*p] can be rearranged to userID2 where 0 <= i; i + (m - 1) * p < n; 1 <= p.

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

Example
userID1 = "acaccaa", userID2 = "aac" and p = 2

Starting at index j = 0 increment i by p = 2 The string formed by concatenating characters userID1[0], userID1[2], userID1[4] is newString = "aac". 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 <= |userID1| <= |userID2| <= (10)**6
• 1 <= p <= (10)**6
• the string userID1 and userID2 only contain lowercase Latin letters