Microsoft - 最长子元素出现次数为偶数的子串

题目描述

输入是一个字符串，要求返回最长子串的长度，要求是子串中每个字母出现次数为偶数。如 bdaaadadb，最长子串为 daaada，长度为 6。

这是微软 2022 年夏天的机试题（对应 2023 届找工作），这题我记忆非常非常深刻。我当时做的时候就感觉真巧妙，后来一直记在心上，毕业之后整理博客想记录一下这题的，还特地问了当时一起参加面试的同学。后来发现自己当时记了题目，真是幸运。

解题思路

代码实现

这里我先给出代码，实在是巧妙。

#include <bits/stdc++.h>

using namespace std;

int main () {
    string s = "mdadac";
    vector<vector<bool> > IsOdd(26, vector<bool>(s.size()+1, false));

    map<unsigned int, int> State;
    vector<unsigned int> IsOddSave;

    for (int i = 0; i < s.size(); ++i) {
        for (int j = 0; j < 26; ++j) {
            IsOdd[j][i+1] = IsOdd[j][i];
        }
        IsOdd[s[i] - 'a'][i+1] = !IsOdd[s[i] - 'a'][i];
        // 将 vector<26> 变为一个 数字
        unsigned int nowvalue = 0;
        for (int j = 0; j < 26; ++j) {
            nowvalue = (nowvalue << 1) + IsOdd[j][i+1];
        }
        State[nowvalue] = i;
        IsOddSave.push_back(nowvalue);
    }

    int result = 0;
    if (State.count(0)) { result = State[0]+1; }
    for (int i = 0; i < s.size(); ++i) {
        unsigned int nowvalue = IsOddSave[i];
        if (State.count(nowvalue)) {
            int maxpos = State[nowvalue];
            result = max(result, maxpos-i);
        }
    }
    cout << result << endl;
}

核心思想

其实就是遍历到第 i 的时候，记录 26 个英文字母的奇偶状态，用一个数字来表示，低 26 位每一个位标识对应字母。那么怎么看 i ~ j 的子串中字母都是偶数，可以想想，这里真的很巧妙，如果字母都是偶数，那么对应的 26 个字母的奇偶状态都是一样的，即数字是一样的！

实现步骤

1. 先遍历一次，算出对应的状态数字，并用一个 Map 映射对应的位置
2. 这样遍历完之后，对于一个状态数字，这个 Map 表记录的是出现这个状态的几个位置中最右边的位置
3. 然后再遍历一次，每次用这个最右边位置减去当前位置，就是以当前位置开头、满足要求的最长子串
4. 最后就能得出真正结果了

Comments