// 2024/09/02
// interviewer: Alisha
// interviewee: Ted

### Q1 ----------------------------------
start time: 11:07

S = "bdaaadadb", the function should return 6.
Substrings in which every letter occurs an even number of times are "aa", "adad", "daaada" and "aaadad".
The length of the longest of them is 6.

bdaad
n^2

dp: [f, f, f, ]
idx: {b: [0], d: [1], a: [2, 3]}

bdaaadadb
l
r

bdaac
l
r

map{b: [0], bd: [1, 3], bda: [2], bdc: [4]}

[b, bd, bda, bdaa, bdaac]

i = 0 : b
i = 1 : b^d
i = 2 : b^d^a
i = 3 : b^d^a^a
i = 4 : b^d^a^a^c
[2,4] = pre[r] ^ pre[l] = b^d^a^a ^ b^d = a^a
xor := (b ^ d ^ a ^ a) ^ (b ^ d)

[l+1, r]
pre[r]-pre[l]

coding brute force - 11:20

int maxEvenString(string& s) {
    n = s.size();
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            string sub = s.substr(i, j - i + 1);
            
            // is even, xor every char in s, if == 0, update ans
            unordered_map<char, int> freq;
            for (char& c: sub) {
                freq[c]++;
            }
            bool isEven = true;
            for (auto [c, f]: freq) {
                if (f % 2 != 0) {
                    isEven = false;
                }
            }
            if (isEven) {
                ans = max(ans, sub.size());
            }
        }
    }
    return ans;
}

// coding approach 2 - 11:59 - 12:03

int maxEvenString(string& s) {
    n = s.size();
    unordered_map<int, int> cnt;
    int x = 0;
    for (int i = 0; i < n; i++) {
        x ^= s[i];
        cnt[x] = i;
    }
    
    x = 0;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        x ^= s[i];
        if (cnt.count(x) == 1) {
            ans = max(cnt.count(x) - i);
        }
    }
    return ans;
}

finish time:

### Q2 ----------------------------------
start time: 11:17

finish time:

### Q3 ----------------------------------
start time:

finish time:

### feedback
1.
2.