Example 1:
Input: history = {1: ["A", "B", "C", "D"], 2: ["X", "D", "B", "A"], 3: ["P", "Q", "R", "S"]}, k = 3, m = 2
Output: [[1, 2]]
Explanation:
Example 2:
Input: history = {1: ["A", "B", "C"], 2: ["C", "B", "A"], 3: ["A", "B", "C"]}, k = 3, m = 3
Output: [[1, 2], [1, 3], [2, 3]]
Explanation:
Example 3:
Input: history = {1: ["A", "B", "C"], 2: ["D", "E", "F"]}, k = 3, m = 1
Output: []
Explanation:
This is a follow-up to Movie History Friends.
Each customer has a list representing the movies they've watched in the order they were viewed. In this variant, two customers are considered "friends" if at least m out of their last k movies are common (not necessarily in the same order or position).
Given a map of customer IDs to their movie watch history, and integers k and m (where m <= k), return all pairs of customer IDs that are friends.
Notes:
k movies in their history, they cannot be friends with anyone.Customer 1's last 3: ["B", "C", "D"]. Customer 2's last 3: ["D", "B", "A"]. They share "B" and "D" (2 movies), which meets m=2. Customer 3 shares no movies with others.
All customers have the same set of last 3 movies (A, B, C), just in different orders. All pairs share 3 movies.
No common movies between the two customers.
1 <= number of customers <= 10001 <= m <= k <= 1000 <= history[i].length <= 1000