Bitmask DP

10038. Maximize the Number of Partitions After Operations

This is the last question of weekly LC contest 379. It can be solved by using bitmask DP.

Using 26 bits as the bit mask for the current status.
Another thing need to maintain is whether we still can change

Approach

dp[curr_status][allow_change] will be converted case by case:
- if allow_change:
- if not allow_change:

Complexity

• Time complexity:
  O(n*2) for sure, each memo it has the bit mask, the value of the bitmask can be 2¹⁶ = 65536
  65536 * 2 10⁴ = 1.2 * 10 ^ 9. I believe not all the bit mask value will be shown, the real complexitiy should be lower than this one.

10038. Maximize the Number of Partitions After Operations

const int NOT_ALLOW = 0, ALLOW = 1;
class Solution {
public:
    int dfs(int i, string &s, int curr_status, int allow_change, vector<vector<unordered_map<int, int>>>& memo, int k){
        
        if (i >= s.size())return curr_status > 0;
        int c = s[i] - 'a';
        if (memo[i][allow_change].find(curr_status) != memo[i][allow_change].end()){
            return memo[i][allow_change][curr_status];
        }
        int ret = 0, this_ret=0;
        int this_status, this_allow_change;
        
        for (int j = 0; j< 26; ++j){
            if (j == c){
                this_allow_change = allow_change;
                }
            else {
                if (allow_change == NOT_ALLOW)continue;
                this_allow_change = NOT_ALLOW;
            }
            this_status = curr_status | (1 << j);
            if (__builtin_popcount(this_status) > k){
                this_ret = 1 + dfs( i +1, s, 1<<j,  this_allow_change, memo, k);
                } else {
                this_ret =  dfs( i +1, s,this_status, this_allow_change, memo, k);
                }
            ret = max(ret, this_ret);
        }
        return memo[i][allow_change][curr_status] = ret;
        
    }
    int maxPartitionsAfterOperations(string s, int k) {
        const int n = s.size();
        vector<vector<unordered_map<int, int>>> memo(n + 1, vector<unordered_map<int, int>>(2));
        int i = 0;
        return dfs(i, s, 0, ALLOW, memo, k);
    }
};