There is a survey that consists of n questions where each question's answer is either 0 (no) or 1 (yes).
The survey was given to m students numbered from 0 to m - 1 and m mentors numbered from 0 to m - 1. The answers of the students are represented by a 2D integer array students where students[i] is an integer array that contains the answers of the ith student (0-indexed). The answers of the mentors are represented by a 2D integer array mentors where mentors[j] is an integer array that contains the answers of the jth mentor (0-indexed).
Each student will be assigned to one mentor, and each mentor will have one student assigned to them. The compatibility score of a student-mentor pair is the number of answers that are the same for both the student and the mentor.
[1, 0, 1] and the mentor's answers were [0, 0, 1], then their compatibility score is 2 because only the second and the third answers are the same.You are tasked with finding the optimal student-mentor pairings to maximize the sum of the compatibility scores.
Given students and mentors, return the maximum compatibility score sum that can be achieved.
Example 1:
Input: students = [[1,1,0],[1,0,1],[0,0,1]], mentors = [[1,0,0],[0,0,1],[1,1,0]] Output: 8 Explanation: We assign students to mentors in the following way: - student 0 to mentor 2 with a compatibility score of 3. - student 1 to mentor 0 with a compatibility score of 2. - student 2 to mentor 1 with a compatibility score of 3. The compatibility score sum is 3 + 2 + 3 = 8.
Example 2:
Input: students = [[0,0],[0,0],[0,0]], mentors = [[1,1],[1,1],[1,1]] Output: 0 Explanation: The compatibility score of any student-mentor pair is 0.
Constraints:
m == students.length == mentors.lengthn == students[i].length == mentors[j].length1 <= m, n <= 8students[i][k] is either 0 or 1.mentors[j][k] is either 0 or 1.Problem Overview: You are given answers from n students and n mentors. Each student must be paired with exactly one mentor. The compatibility score for a pair equals the number of positions where their answers match. The goal is to assign pairs so the total compatibility score is maximized.
Approach 1: Backtracking with Permutations (Time: O(n! * n * m), Space: O(n))
This approach tries every possible assignment of students to mentors. For each permutation of mentors, compute the compatibility score by comparing answers position-by-position. Use backtracking to generate permutations while tracking which mentors are already used. At each step, add the score for the current student-mentor pair and recurse to the next student. Since there are n! permutations and computing each score requires iterating over m answers, the total complexity becomes O(n! * n * m). This works because n ≤ 8, but it still explores many redundant states.
Approach 2: Dynamic Programming with Bitmasking (Time: O(n * 2^n + n^2 * m), Space: O(2^n))
The optimal solution treats mentor assignments as a bitmask state. First precompute a compatibility matrix where score[i][j] stores the match score between student i and mentor j. Then use dynamic programming where a mask represents which mentors are already assigned. If a mask has k bits set, it means the first k students are already matched. Iterate through mentors not in the mask, assign one to the next student, and update the DP value. Bit operations efficiently track used mentors, making this a classic bitmask DP pattern. The state space is 2^n, and each state tries up to n mentors.
Recommended for interviews: Start by explaining the permutation-based backtracking solution to show the brute-force search space. Then transition to the bitmask dynamic programming optimization. Interviewers usually expect the O(n * 2^n) DP solution because it demonstrates familiarity with state compression and efficient subset transitions.
This approach involves generating all possible permutations of mentor assignments for the students. We calculate the compatibility score for each permutation and keep track of the maximum score found. This method exhaustively tries each possible pairing and selects the optimal one.
This Python solution uses the itertools.permutations function to produce all possible assignments of m mentors to m students. For each permutation, it calculates the total compatibility score by summing up individual scores of assigned student-mentor pairs. The maximum score is updated whenever a new higher score is found.
The time complexity is O((m!) * m * n), where m is the number of students and n is the number of questions. The space complexity is O(m!).
This approach uses dynamic programming with bitmasking to efficiently calculate the maximum compatibility score. The DP state is represented as a bitmask that keeps track of which mentors have already been assigned to a student, optimizing both time and space usage.
This C++ solution uses dynamic programming with bitmasking. The dp array is used to store the maximum compatibility scores for different combinations of assigned mentors (represented as bitmask states). The findMaxScore function is a recursive function that attempts to assign available mentors (those not set in the mask) to the current student and recursively solves subproblems.
The time complexity is O(m * (2^m) * n), and the space complexity is O(2^m).
We can first preprocess the compatibility score g[i][j] between each student i and mentor j, and then use a backtracking algorithm to solve the problem.
Define a function dfs(i, s), where i represents the current student being processed, and s represents the current sum of compatibility scores.
In dfs(i, s), if i geq m, it means all students have been assigned, and we update the answer to max(ans, s). Otherwise, we enumerate which mentor the i-th student can be assigned to, and then recursively process the next student. During the process, we use an array vis to record which mentors have already been assigned to avoid duplicate assignments.
We call dfs(0, 0) to get the maximum compatibility score sum.
The time complexity is O(m!), and the space complexity is O(m^2). Here, m is the number of students and mentors.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Backtracking with Permutations | The time complexity is O((m!) * m * n), where |
| Dynamic Programming with Bitmasking | The time complexity is O(m * (2^m) * n), and the space complexity is O(2^m). |
| Preprocessing + Backtracking | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Permutations | O(n! * n * m) | O(n) | Small input sizes where brute force is acceptable and useful for understanding all pair assignments |
| Dynamic Programming with Bitmasking | O(n * 2^n + n^2 * m) | O(2^n) | Optimal solution for n ≤ 8; reduces factorial search to subset DP using bitmask states |
LeetCode 1947. Maximum Compatibility Score Sum | 🏆 Weekly Contest 251 | Explained • Cherry Coding [IIT-G] • 2,571 views views
Watch 8 more video solutions →Practice Maximum Compatibility Score Sum with our built-in code editor and test cases.
Practice on FleetCode