Python | Tracking Positions | O(n), O(1) | Beats 98%
CodeComplexity

Time complexity: O(n). Loops over all pos in s, n total. Each iteration is constant time so n overall.


Space complexity: O(1). last_pos has le
# Code
```python3 []
class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        substrs = 0
        last_pos = [-1] * 3 # position of [a, b, c]
        for pos in range(len(s)):
            last_pos[ord(s[pos]) - ord("a")] = pos # update index for current char

            # if no valid substsr, 1 + (-1) so 0
            # else, + 1 for current str, + min(last_pos) for chars before current substr as variants
            substrs += 1 + min(last_pos)

        return substrs
```

# Complexity
- Time complexity: $$O(n)$$. Loops over all pos in s, n total. Each iteration is constant time so n overall.

- Space complexity: $$O(1)$$. last_pos has length of 3, other variables are constant space, so constant overall.

# Performance

![Screenshot (9).png](https://assets.leetcode.com/users/images/fbf2e910-6169-4109-939b-a6ab4a628b64_1741654720.9841323.png)

['Python3']