[C++] Binary Search Solution
I realized that this problem can be solved by sliding windows after the contest...\ncpp\nclass Solution {\npublic:\n\t// Time Complexity: O(n lgn)\n\t// Space C
I realized that this problem can be solved by sliding windows after the contest...\n```cpp\nclass Solution {\npublic:\n\t// Time Complexity: O(n lgn)\n\t// Space Complexity: O(n)\n    int numberOfSubstrings(string s) {\n        vector<vector<int>> abc(3);\n        int ans(0);\n\t\t\n\t\t// record indices\n        for (int i = 0; i < s.length(); ++i)\n            abc[s[i] - \'a\'].push_back(i);\n        \n\t\tfor (int i = 0; i < s.length(); ++i) {\n\t\t\t// find other 2 letters given s[i]\n            int x((s[i] - \'a\' + 1) % 3), y((s[i] - \'a\' + 2) % 3);\n\t\t\t// search the min index of two letters\n            vector<int>::iterator lx(lower_bound(abc[x].begin(), abc[x].end(), i + 1)), ly(lower_bound(abc[y].begin(), abc[y].end(), i + 1));\n\t\t\t// if both found, increment the answer\n            if (lx != abc[x].end() && ly != abc[y].end())\n                ans += s.length() - max(*lx, *ly);\n        }\n        return ans;\n    }\n};\n```
[]