Substring Counts in O(N) || Brute-Force vs. Optimal Approach Explanation || Code & Insights
Intuition\nWhen tasked with finding the number of substrings in a string that contain all three distinct characters (\'a\', \'b\', and \'c\'), a naive approach 
### Intuition\nWhen tasked with finding the number of substrings in a string that contain all three distinct characters (\'a\', \'b\', and \'c\'), a naive approach might involve generating all possible substrings and checking each one, leading to a time complexity of \\(O(n^3)\\). This method would be inefficient, particularly for longer strings.\n\n### Approach\nTo solve this problem efficiently, we can employ a sliding window technique combined with tracking the last seen indices of each character:\n\n1. **Tracking Last Seen Indices**:\n   - We maintain an array `lastSeen` of size 3, where:\n     - `lastSeen[0]` tracks the last position of \'a\'.\n     - `lastSeen[1]` tracks the last position of \'b\'.\n     - `lastSeen[2]` tracks the last position of \'c\'.\n\n2. **Iterating Through the String**:\n   - As we iterate through the string, we update the position of each character in the `lastSeen` array.\n\n3. **Calculating Valid Substrings**:\n   - For each character, the number of valid substrings that can end at the current position is determined by the minimum index from `lastSeen`. This count is calculated using:\n   \\[\n   \\text{valid substrings} = 1 + \\text{minimum index of last seen characters}\n   \\]\n   - This formula is valid as all substrings that start from indices before or at the earliest last seen index and end at the current position will contain all three characters.\n\n4. **Updating the Answer**:\n   - Accumulate the count of valid substrings for each character position to get the total number.\n\n### Example\nConsider the string "abc":\n\n- Initial `lastSeen`: `[-1, -1, -1]` (no characters seen).\n- At index 0 (character \'a\'):\n  - Update `lastSeen`: `[0, -1, -1]`.\n  - Valid substrings = `1 + min(0, -1, -1) = 1`.\n- At index 1 (character \'b\'):\n  - Update `lastSeen`: `[0, 1, -1]`.\n  - Valid substrings = `1 + min(0, 1, -1) = 0`.\n- At index 2 (character \'c\'):\n  - Update `lastSeen`: `[0, 1, 2]`.\n  - Valid substrings = `1 + min(0, 1, 2) = 1 + 0 = 1` (only the substring "abc").\n\nTotal valid substrings found: 1.\n\n### Edge Cases\n- **Strings with Less Than 3 Characters**: If the string length is less than 3, no substrings can contain all three characters. Hence, the result should be 0.\n- **Strings Missing Characters**: If any of \'a\', \'b\', or \'c\' are absent from the string, valid substrings cannot be formed. For example, "aabb" contains only \'a\' and \'b\', resulting in 0 valid substrings.\n\nThis approach is efficient, boasting a time complexity of \\(O(n)\\) and a space complexity of \\(O(1)\\), making it suitable for larger strings.\n\n### Complexity\n- **Time Complexity**: \\(O(n)\\) - The string is traversed once, with constant-time operations for updates and calculations.\n- **Space Complexity**: \\(O(1)\\) - The space used is constant, as the `lastSeen` array has a fixed size of 3 regardless of input size.\n\n\n\n# Code\n``` cpp []\nclass Solution {\npublic:\n    int numberOfSubstrings(string s) {\n        vector<int> lastseen(3, -1);\n        int ans = 0;\n\n        for(int i = 0; i < s.size(); i++){\n            lastseen[s[i] - \'a\'] = i;\n\n            ans += 1 + *min_element(lastseen.begin(), lastseen.end());\n        }\n\n        return ans;\n    }\n};\n```\n``` java []\npublic class Solution {\n    public int numberOfSubstrings(String s) {\n        int[] lastseen = new int[3];\n        Arrays.fill(lastseen, -1);\n        int ans = 0;\n        \n        for (int i = 0; i < s.length(); i++) {\n            lastseen[s.charAt(i) - \'a\'] = i;\n\n            ans += 1 + Math.min(lastseen[0], Math.min(lastseen[1], lastseen[2]));\n        }\n        return ans;\n    }\n}\n```\n```python3 []\nclass Solution:\n    def numberOfSubstrings(self, s: str) -> int:\n        lastseen = [-1] * 3\n        ans = 0\n\n        for i in range(len(s)):\n            lastseen[ord(s[i]) - ord(\'a\')] = i\n            min_index = min(lastseen)\n            ans += 1 + min_index\n        \n        return ans\n```
['String', 'Sliding Window', 'C++', 'Java', 'Python3']