c++ from brute force to optimal
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code brute force, ETL\n```\n    bool isGoodStr(bool* flags, int n){\n        int count = 0;\n        for(int i=0; i<n; i++){\n            if(flags[i] == false)\n                count++;\n        }\n        return count == 0 || count == 1;\n    }\n    int longestAwesome(string s) {\n        int maxlen = 0;\n        for(int i=0; s.length() - i > maxlen; i++){\n            bool flags[10] = {true, true, true, true, true, true, true, true, true, true};// 0 ,1, 2, ... , 9\n            for(int j=i; j<s.length(); j++){\n                flags[s[j]-\'0\'] = !flags[s[j]-\'0\'];\n                if(isGoodStr(flags, 10))\n                    maxlen = max(maxlen, j-i+1);\n            }\n        } \n        return maxlen;\n    }\n```\n\n# Code improve brute force, 19 ms\n```\n    bool checkBitsIsAwesome(int bits) {\n        if (bits == 0 || bits == 512 || bits == 256 || bits == 128 || bits == 64 || bits == 32 || bits == 16 || bits == 8 || bits == 4 || bits == 2 || bits == 1)\n            return true;\n        return false;\n    }\n    bool shouldStop(int bits, const int bitmap[], const int endIdx[], int size, int idx, string& s) {\n        int invalid_cnt = 0;\n        for (int i = 0; i < size; i++) {\n            if ((bits & bitmap[i]) && (idx > endIdx[i]))\n               invalid_cnt++;\n            if (invalid_cnt > 1)\n                return true;\n        }\n        return false;\n    }\n    int longestAwesome(string s) {\n        int maxlen = 1;\n        int bitmap[10] = { 512, 256, 128, 64, 32, 16, 8, 4, 2, 1 };// 0 ,1, 2, ... , 9\n        int endIdx[10] = {0};// 0 ,1, 2, ... , 9\n        vector<int> prefix_string_bits(s.length(), 0);\n        prefix_string_bits[0] = bitmap[s[0] - \'0\'];\n        for (int i = 1; i < s.length(); i++) {\n            endIdx[s[i] - \'0\'] = i;\n            prefix_string_bits[i] = prefix_string_bits[i - 1] ^ bitmap[s[i] - \'0\'];\n            if (checkBitsIsAwesome(prefix_string_bits[i]))\n                maxlen = max(maxlen, i + 1);\n        }\n\n        for (int i = 1; i < s.length() - maxlen; i++) {\n            int prev_bits = prefix_string_bits[i + maxlen - 1] ^ prefix_string_bits[i - 1];\n            for (int j = i + maxlen; j < s.length(); j++) {\n                prev_bits = prev_bits ^ bitmap[s[j] - \'0\'];\n                if (shouldStop(prev_bits, bitmap, endIdx, 10, j, s))\n                    break;\n                if (checkBitsIsAwesome(prev_bits))\n                    maxlen = max(maxlen, j - i + 1);\n            }\n        }\n        return maxlen;\n    }\n```\n\n\n# Code the optimal solution 17ms\n```\n    int longestAwesome(string s) {\n        int maxlen = 0, prefixArray_bits = 0;\n        vector<int> leftmost_bitmap(1024, s.size());\n        leftmost_bitmap[0] = -1;\n        for (int i = 0; i < s.size(); i++) {\n            prefixArray_bits = prefixArray_bits ^ (1 << (s[i] - \'0\'));\n            for (int j = 0; j < 10; j++)\n                maxlen = max(maxlen, i - leftmost_bitmap[prefixArray_bits ^ (1 << j)]);\n            maxlen = max(maxlen, i - leftmost_bitmap[prefixArray_bits]);\n            leftmost_bitmap[prefixArray_bits] = min(leftmost_bitmap[prefixArray_bits], i);\n        }\n        return maxlen;\n    }\n```
['C++']