Leetcode | Maximum Compatibility Score Sum | Java

devstromo · devstromo · commit 35f87d1ad82d · 2025-04-27T22:47:26.000-03:00
diff --git a/leetcode/src/main/java/com/devstromo/medium/p1947/DESCRIPTION.md b/leetcode/src/main/java/com/devstromo/medium/p1947/DESCRIPTION.md
@@ -0,0 +1,38 @@
+# 1947. Maximum Compatibility Score Sum
+
+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.
+
+- For example, if the student's answers were `[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.length`
+- `n == students[i].length == mentors[j].length`
+- `1 <= m, n <= 8`
+- `students[i][k]` is either `0` or `1`.
+- `mentors[j][k]` is either `0` or `1`.
diff --git a/leetcode/src/main/java/com/devstromo/medium/p1947/Solution.java b/leetcode/src/main/java/com/devstromo/medium/p1947/Solution.java
@@ -0,0 +1,39 @@
+package com.devstromo.medium.p1947;
+
+public class Solution {
+    public int maxCompatibilitySum(int[][] students, int[][] mentors) {
+        int m = students.length;
+        int n = students[0].length;
+
+        // Precompute compatibility scores
+        int[][] score = new int[m][m];
+        for (int i = 0; i < m; i++) {
+            for (int j = 0; j < m; j++) {
+                int match = 0;
+                for (int k = 0; k < n; k++) {
+                    if (students[i][k] == mentors[j][k]) {
+                        match++;
+                    }
+                }
+                score[i][j] = match;
+            }
+        }
+
+        // dp[mask]: max score with mentors assigned as in mask
+        int[] dp = new int[1 << m];
+
+        for (int mask = 0; mask < (1 << m); mask++) {
+            int studentIndex = Integer.bitCount(mask); // how many students have been assigned
+            if (studentIndex >= m) continue;
+
+            for (int j = 0; j < m; j++) {
+                if ((mask & (1 << j)) == 0) { // mentor j not yet assigned
+                    int nextMask = mask | (1 << j);
+                    dp[nextMask] = Math.max(dp[nextMask], dp[mask] + score[studentIndex][j]);
+                }
+            }
+        }
+
+        return dp[(1 << m) - 1];
+    }
+}
diff --git a/leetcode/src/test/java/com/devstromo/medium/p1947/SolutionUnitTest.java b/leetcode/src/test/java/com/devstromo/medium/p1947/SolutionUnitTest.java
@@ -0,0 +1,39 @@
+package com.devstromo.medium.p1947;
+
+import org.junit.jupiter.api.DisplayName;
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class SolutionUnitTest {
+    private final Solution solution = new Solution();
+
+    @Test
+    @DisplayName("Test Maximum Compatibility Score Sum")
+    void testMaximumCompatibilityScoreSum() {
+        assertEquals(8, solution.maxCompatibilitySum(
+                new int[][]{
+                        {1, 1, 0},
+                        {1, 0, 1},
+                        {0, 0, 1}
+                },
+                new int[][]{
+                        {1, 0, 0},
+                        {0, 0, 1},
+                        {1, 1, 0}
+                }
+        ));
+        assertEquals(0, solution.maxCompatibilitySum(
+                new int[][]{
+                        {0, 0},
+                        {0, 0},
+                        {0, 0},
+                },
+                new int[][]{
+                        {1, 1},
+                        {1, 1},
+                        {1, 1},
+                }
+        ));
+    }
+}
