Maximum compatibility score sum

Array Dynamic Programming Backtracking Bit Manipulation Bitmask

64.3% acceptance

Feb 25, 2026

832

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. 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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn max_compatibility_sum(students: Vec<Vec<i32>>, mentors: Vec<Vec<i32>>) -> i32 {
    let m = students.len();
    let n = students[0].len();

    // Precompute compatibility scores
    let mut score = vec![vec![0; m]; m];
    for i in 0..m {
      for j in 0..m {
        for k in 0..n {
          if students[i][k] == mentors[j][k] {
            score[i][j] += 1;
          }
        }
      }
    }

    // Bitmask DP: dp[mask] = max score using mentors indicated by mask for first popcount(mask) students
    let mut dp = vec![0i32; 1 << m];
    for mask in 1..(1 << m) {
      let student = (mask as u32).count_ones() as usize - 1;
      for j in 0..m {
        if mask & (1 << j) != 0 {
          dp[mask] = dp[mask].max(dp[mask ^ (1 << j)] + score[student][j]);
        }
      }
    }
    dp[(1 << m) - 1]
  }
}