String and bit manipulation

Using bitmask to solve the string problems

1371. Find the Longest Substring Containing Vowels in Even Counts

Solutions

class Solution {
public:
    int findTheLongestSubstring(string s) {
        unordered_map<int, int> mask_i;
        mask_i[0] = -1;
        int curr = 0;
        map<char, int> vowels = {{'a',1}, {'e', 2}, {'i', 3}, {'o', 4}, {'u', 5}};
        const int n = s.length();
        int ret = 0;
        for (int i = 0; i < n; ++i)
        {
            if (vowels.count(s[i]))
            {
                int bit_pos = vowels[s[i]];
                curr ^= (1<<bit_pos);  
            }
            if(mask_i.count(curr)) ret = max(ret, i - mask_i[curr]);
            else mask_i[curr] = i;
        }
        return ret;
        
    }
};

Change the map to a vector can make it much faster

class Solution {
public:
    int findTheLongestSubstring(string s) {
        vector<int> mask_i(1<<5, INT_MAX);
        mask_i[0] = -1;
        int curr = 0;
        map<char, int> vowels = {{'a',0}, {'e', 1}, {'i', 2}, {'o', 3}, {'u', 4}};
        const int n = s.length();
        int ret = 0;
        for (int i = 0; i < n; ++i)
        {
            if (vowels.count(s[i]))
            {
                int bit_pos = vowels[s[i]];
                curr ^= (1<<bit_pos);  
            }
            if(mask_i[curr] != INT_MAX) ret = max(ret, i - mask_i[curr]);
            else mask_i[curr] = i;
        }
        return ret;
        
    }
};

1542. Find Longest Awesome Substring

const int INF = 1e9;
class Solution {
public:
    int longestAwesome(string s) 
    {
        vector<int> mask_i(1<<10, INF);
        mask_i[0] = -1;
        int mask = 0;
        int mask_with_one_bit_diff = 0;
        int ret = 1;
        for (int i = 0; i < s.length(); ++i)
        {
            mask ^= 1<<(s[i] - '0');
            // update mask_i and get the all even numbers case result
            if (mask_i[mask]==INF)mask_i[mask] = i;
            else ret = max(ret, i - mask_i[mask]);
            
            // one odd number
            for (int j =0; j < 10; ++j)
            {
                mask_with_one_bit_diff = mask^(1<<j);
                if (mask_i[mask_with_one_bit_diff] != INF)
                    ret = max(ret, i - mask_i[mask_with_one_bit_diff]);
            }
        }
        return ret;
    }
};