[Java] ELEGANT No Sliding Window EXPLAINED (No of Sub-Strings Ending at Curr Index)
Okay so these questions look like they have sliding window, But in this one i figured out something else.\nTake three pointers l1, l2, l3 for a, b and c respect
Okay so these questions look like they have sliding window, But in this one i figured out something else.\nTake three pointers l1, l2, l3 for a, b and c respectively.\nNow as you iterate over the string of length n, you can count the number of sub-strings ending at that particular index.\nHow can we do that is here ->\n* Keep on updating l1, l2 and l3.\n* And take the minimum of l1, l2 and l3.\n* Now from this min-index (min(l1, l2, l3) to the curr index i this is the smallest possible sub-string ending at curr-index i which follows the constraint.\n* If the smallest sub-string is from min-index to curr-index, then for every sub-string starting from index 0, 1, 2, 3, ......min-index and ending at curr-index is valid, (So how many are these...... So there are min-index + 1 sub-strings)\n* Add this min-index + 1 to the count.\n```\nclass Solution {\n    public int numberOfSubstrings(String s) {\n        int n = s.length(), count = 0;\n        int l1 = -1, l2 = -1, l3 = -1;\n        for(int i = 0; i < n; i++) {\n            if(s.charAt(i) == \'a\') l1 = i;\n            else if(s.charAt(i) == \'b\') l2 = i;\n            else l3 = i;\n            if(l1 == -1 || l2 == -1 || l3 == -1) continue;\n            int min = Math.min(l1, Math.min(l2, l3));\n            count += min + 1;\n        }\n        return count;\n    }\n}
[]