Clear Explanation | Java | Sliding Window | No HashMap Used | Beginner Approach | Beats 60 % ✨ |
Intuition\nThe First Intuition was to track the total count of a, b, and c characters in our substring. As soon as we find a substring that has atleast one occu
# Intuition\nThe First Intuition was to track the total count of a, b, and c characters in our substring. As soon as we find a substring that has atleast one occurence of each, we do not have to iterate further and can simply add the total such substrings (with atleast one occurence) from that ***start(pointer i)*** by adding to our result the substrings that can be formed by remaining elements ***(String.length - end (pointer j))***\n\n# Approach\n**Step 1: Track Character Counts:** Use three counters to keep track of the number of \'a\', \'b\', and \'c\' characters in the current window or curr Substring.\n\n**Step 2: Expand the Window:** Start with both pointers i and j at the beginning of the string i.e $$Index$$ $$0$$.\nMove the end pointer j to expand the window, updating the counts of \'a\', \'b\', and \'c\'.\n\n**Step 3: Check Validity:** Whenever the current window contains at least one \'a\', \'b\', and \'c\', it is a valid window.\n\n**Step 4: Count Valid Substrings:** If a valid window is found, all substrings starting from ***i (Curr Start)*** and ending anywhere from ***(Curr End) j*** to the end of the string are valid. \n\nThe number of such substrings is ***s.length() - j***.\n\n***FOR EXAMPLE*** \n**String** - a | b | c | a | b | c\nif **Start $$(i)$$= 0**, \nFirst Valid Window, is found at **$$index = 2$$**\nSo No. of Total Valid Substrings from **$$0$$** will be **$$S.length() - j = 6-2 = 4$$**\n\n**This can be observed as follows:**\n1. a | b | c \n2. a | b | c | a \n3. a | b | c | a | b\n4. a | b | c | a | b | c\n\n**Step 4: Shrink the Window:** Move the start pointer i to the right to reduce the window size, reduce the count of Char at the previous Start and continue checking for other valid windows.\n\n\n# Complexity\n- Time complexity: $$O(n)$$\n\n- Space complexity: $$O(1)$$\n\n# Code\n```\nclass Solution {\n    public int numberOfSubstrings(String s) {\n        int aTot = 0, bTot = 0, cTot = 0; // to track the count of \'a\', \'b\', \'c\'\n        int res = 0;\n        int i = 0, j = 0;\n    \n        while (j < s.length()) {\n            // Expand the window by including s[j]\n            if (s.charAt(j) == \'a\') aTot++;\n            else if (s.charAt(j) == \'b\') bTot++;\n            else if (s.charAt(j) == \'c\') cTot++;\n    \n            // Check if the current window has at least one \'a\', \'b\', and \'c\'\n            while (aTot > 0 && bTot > 0 && cTot > 0) {\n                // If valid, count all substrings starting from i to the end\n                res += s.length() - j;\n    \n                // Move the start of the window forward to reduce the window size\n                if (s.charAt(i) == \'a\') aTot--;\n                else if (s.charAt(i) == \'b\') bTot--;\n                else if (s.charAt(i) == \'c\') cTot--;\n                \n                i++; // Move the start pointer\n            }\n            \n            j++; // Move the end pointer\n        }\n        return res;\n    }\n}\n```
['String', 'Sliding Window', 'Java']