True subquadratic complexity using a bit of number theory :)
ApproachThere is a closed form for the two final digits - they are given by summing digits of s multiplied by binomial coefficients, similar to Pascal's triangl
# Approach
There is a closed form for the two final digits - they are given by summing digits of `s` multiplied by binomial coefficients, similar to Pascal's triangle.

This can be leveraged to get log-linear time complexity and logarithmic space complexity. This is a situation where we can't just assume all arithmetic operations take constant time, since central binomial coefficients grow exponentially as $n \to \infty$. Some care is required - computing all full binomial coefficients necessarily takes superlinear time, as the space to even store them all is superlinear in $|s|$.

Luckily, we only need them modulo $10$. We can generate them all mod $10$ using a bit of number-theoretic fiddling, writing each binomial coefficient in the form $2^a \cdot 5^b \cdot m$ where $m$ is coprime to $10$.

This approach scales well to very large inputs. Here are some benchmarks:


| $\lvert s \rvert$    | Time              |
| ---------------------|------------------ |
| 10                   | 8.6 μs ± 105 ns   |
| 100                  | 104 μs ± 628 ns   |
| 1000                 | 1.13 ms ± 3.22 μs |
| 10000                | 12 ms ± 41.7 μs   |
| 100000               | 123 ms ± 1.58 ms  |
| 1000000              | 1.22 s ± 16.3 ms  |
| 10000000             | 12.4 s ± 47.5 ms  |



# Complexity
- Time complexity: $\mathcal O(\lvert s \rvert \log^2 \lvert s \rvert)$ is the easiest bound I can see for this algorithm. Probably this analysis can be tightened by exploiting the scarcity of large powers of $2$ or $5$.

- Space complexity: $\mathcal O(\log \lvert s \rvert)$

# Code
```python3 []
# generate all binomial coefficients C(n, k) mod 10
def binoms_mod10(n):
    a = b = 0
    m = 1
    yield 1
    for j in range(1, n + 1):
        # morally, `m = m * (n + 1 - j) / j`
        pa, pb, mm = decompose(n + 1 - j)
        ma, mb, dm = decompose(j)
        a += pa - ma
        b += pb - mb
        m = m * mm * pow(dm, -1, 10) % 10
        yield m * pow(2, a, 10) * pow(5, b, 10) % 10

# write k in the form 2^a 5^b m, with m coprime to 10
def decompose(k):
    a = b = 0
    while k % 2 == 0:
        k //= 2
        a += 1
    while k % 5 == 0:
        k //= 5
        b += 1
    return a, b, k

class Solution:
    def hasSameDigits(self, s: str) -> bool:
        s1 = s2 = 0
        for binom, (a, b) in zip(binoms_mod10(len(s) - 2), pairwise(map(int, s))):
            s1 += binom * a
            s2 += binom * b
        return (s1 - s2) % 10 == 0
```


Since we actually know the input is guaranteed to be tiny, we can solve it very very quickly by just pre-computing a table of all binomial coefficients mod $10$. We need to do a bit of compression to make it small enough to submit.

```python3 []
tab=[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,0,0,5,1],[1,6,5,0,5,6,1],[1,7,1,5,5,1,7,1],[1,8,8,6,0,6,8,8,1],[1,9,6,4,6,6,4,6,9,1],[1,0,5,0,0,2,0,0,5,0,1],[1,1,5,5,0,2,2,0,5,5,1,1],[1,2,6,0,5,2,4,2,5,0,6,2,1],[1,3,8,6,5,7,6,6,7,5,6,8,3,1],[1,4,1,4,1,2,3,2,3,2,1,4,1,4,1],[1,*[5]*4,3,*[5]*4,3,*[5]*4,1],[1,6,*[0]*3,8,8,*[0]*3,8,8,*[0]*3,6,1],[1,7,6,0,0,8,6,8,0,0,8,6,8,0,0,6,7,1],[1,8,3,6,0,8,4,4,8,0,8,4,4,8,0,6,3,8,1],[1,9,1,9,6,8,2,8,2,8,8,2,8,2,8,6,9,1,9,1],[1,*[0]*3,5,4,*[0]*4,6,*[0]*4,4,5,*[0]*3,1],[1,1,0,0,5,9,4,*[0]*3,6,6,*[0]*3,4,9,5,0,0,1,1],[1,2,1,0,5,4,3,4,0,0,6,2,6,0,0,4,3,4,5,0,1,2,1],[1,3,3,1,5,9,7,7,4,0,6,8,8,6,0,4,7,7,9,5,1,3,3,1],[*[1,4,6,4,6,4,6,4]*3,1],[1,*[5,0,0,0,0,0,0,5]*3,1],[1,6,5,*[0]*5,5,0,5,*[0]*5,5,0,5,*[0]*5,5,6,1],[1,7,1,5,*[0]*4,*[5]*4,*[0]*4,*[5]*4,*[0]*4,5,1,7,1],[1,8,8,6,*[5,0,0,0]*5,5,6,8,8,1],[1,9,6,4,1,*[5,0,0,5]*5,1,4,6,9,1],[1,0,5,0,5,6,*[5,0]*9,5,6,5,0,5,0,1],[1,1,*[5]*3,1,1,*[5]*18,1,1,*[5]*3,1,1],[1,2,6,0,0,6,2,6,*[0]*17,6,2,6,0,0,6,2,1],[1,3,8,6,0,6,8,8,6,*[0]*16,6,8,8,6,0,6,8,3,1],[1,4,1,4,6,6,4,6,4,6,*[0]*15,6,4,6,4,6,6,4,1,4,1],[1,*[5]*3,0,2,*[0]*4,6,*[0]*14,6,*[0]*4,2,0,*[5]*3,1],[1,6,0,0,5,2,2,*[0]*3,6,6,*[0]*13,6,6,*[0]*3,2,2,5,0,0,6,1],[1,7,6,0,5,7,4,2,0,0,6,2,6,*[0]*12,6,2,6,0,0,2,4,7,5,0,6,7,1],[1,8,3,6,5,2,1,6,2,0,6,8,8,6,*[0]*11,6,8,8,6,0,2,6,1,2,5,6,3,8,1],[1,9,1,9,1,7,3,7,8,2,6,4,6,4,6,*[0]*10,6,4,6,4,6,2,8,7,3,7,1,9,1,9,1],[1,*[0]*4,8,0,0,5,0,8,*[0]*4,6,*[0]*9,6,*[0]*4,8,0,5,0,0,8,*[0]*4,1],[1,1,*[0]*3,8,8,0,5,5,8,8,*[0]*3,6,6,*[0]*8,6,6,*[0]*3,8,8,5,5,0,8,8,*[0]*3,1,1],[1,2,1,0,0,8,6,8,5,0,3,6,8,0,0,6,2,6,*[0]*7,6,2,6,0,0,8,6,3,0,5,8,6,8,0,0,1,2,1],[1,3,3,1,0,8,4,4,3,5,3,9,4,8,0,6,8,8,6,*[0]*6,6,8,8,6,0,8,4,9,3,5,3,4,4,8,0,1,3,3,1],[1,4,6,4,1,8,2,8,7,8,8,2,3,2,8,6,4,6,4,6,*[0]*5,6,4,6,4,6,8,2,3,2,8,8,7,8,2,8,1,4,6,4,1],[1,5,0,0,5,9,0,0,5,5,6,0,5,5,0,4,*[0]*4,6,*[0]*4,6,*[0]*4,4,0,5,5,0,6,5,5,0,0,9,5,0,0,5,1],[1,6,5,0,5,4,9,0,5,0,1,6,5,0,5,4,4,*[0]*3,6,6,*[0]*3,6,6,*[0]*3,4,4,5,0,5,6,1,0,5,0,9,4,5,0,5,6,1],[1,7,1,5,5,9,3,9,5,5,1,7,1,5,5,9,8,4,0,0,6,2,6,0,0,6,2,6,0,0,4,8,9,5,5,1,7,1,5,5,9,3,9,5,5,1,7,1],[1,8,8,6,0,4,2,2,4,0,6,8,8,6,0,4,7,2,4,0,6,8,8,6,0,6,8,8,6,0,4,2,7,4,0,6,8,8,6,0,4,2,2,4,0,6,8,8,1],[1,9,*[6,4]*7,1,9,*[6,4]*3,6,*[6,4]*3,6,9,1,*[4,6]*7,9,1],[1,0,5,*[0]*13,5,0,5,*[0]*6,2,*[0]*6,5,0,5,*[0]*13,5,0,1],[1,1,5,5,*[0]*12,*[5]*4,*[0]*5,2,2,*[0]*5,*[5]*4,*[0]*12,5,5,1,1],[1,2,6,0,5,*[0]*11,5,*[0]*3,5,*[0]*4,2,4,2,*[0]*4,5,*[0]*3,5,*[0]*11,5,0,6,2,1],[1,3,8,6,5,5,*[0]*10,5,5,0,0,5,5,*[0]*3,2,6,6,2,*[0]*3,5,5,0,0,5,5,*[0]*10,5,5,6,8,3,1],[1,4,1,4,1,0,5,*[0]*9,*[5,0]*4,0,2,8,2,8,2,0,*[0,5]*4,*[0]*9,5,0,1,4,1,4,1],[1,*[5]*4,1,5,5,*[0]*8,*[5]*8,0,2,*[0]*4,2,0,*[5]*8,*[0]*8,5,5,1,*[5]*4,1],[1,6,*[0]*3,6,6,0,5,*[0]*7,5,*[0]*7,5,2,2,*[0]*3,2,2,5,*[0]*7,5,*[0]*7,5,0,6,6,*[0]*3,6,1],[1,7,6,0,0,6,2,6,5,5,*[0]*6,5,5,*[0]*6,5,7,4,2,0,0,2,4,7,5,*[0]*6,5,5,*[0]*6,5,5,6,2,6,0,0,6,7,1],[1,8,3,6,0,6,8,8,1,0,5,*[0]*5,5,0,5,*[0]*5,5,2,1,6,2,0,2,6,1,2,5,*[0]*5,5,0,5,*[0]*5,5,0,1,8,8,6,0,6,3,8,1],[1,9,1,9,6,6,4,6,9,1,5,5,*[0]*4,*[5]*4,*[0]*4,5,7,3,7,8,2,2,8,7,3,7,5,*[0]*4,*[5]*4,*[0]*4,5,5,1,9,6,4,6,6,9,1,9,1],[1,*[0]*3,5,2,0,0,5,0,6,*[0,5,0,0]*3,0,5,2,0,0,5,0,4,0,5,0,0,2,*[5,0,0,0]*3,5,0,6,0,5,0,0,2,5,*[0]*3,1],[1,1,0,0,5,7,2,0,5,5,6,6,*[5,5,0,0]*3,5,7,2,0,5,5,4,4,5,5,0,2,7,*[5,0,0,5]*3,5,6,6,5,5,0,2,7,5,0,0,1,1],[1,2,1,0,5,2,9,2,5,0,1,2,1,*[0,5]*6,2,9,2,5,0,9,8,9,0,5,2,9,2,*[5,0]*6,1,2,1,0,5,2,9,2,5,0,1,2,1],[1,3,3,1,5,7,1,1,7,5,1,3,3,1,*[5]*11,7,1,1,7,5,9,7,7,9,5,7,1,1,7,*[5]*11,1,3,3,1,5,7,1,1,7,5,1,3,3,1],[1,4,6,4,6,2,8,2,8,2,6,4,6,4,6,*[0]*10,2,8,2,8,2,4,6,4,6,4,2,8,2,8,2,*[0]*10,6,4,6,4,6,2,8,2,8,2,6,4,6,4,1],[1,5,*[0]*3,8,*[0]*4,8,*[0]*4,6,*[0]*9,2,*[0]*4,6,*[0]*4,6,*[0]*4,2,*[0]*9,6,*[0]*4,8,*[0]*4,8,*[0]*3,5,1],[1,6,5,0,0,8,8,*[0]*3,8,8,*[0]*3,6,6,*[0]*8,2,2,*[0]*3,6,6,*[0]*3,6,6,*[0]*3,2,2,*[0]*8,6,6,*[0]*3,8,8,*[0]*3,8,8,0,0,5,6,1],[1,7,1,5,0,8,6,8,0,0,8,6,8,0,0,6,2,6,*[0]*7,2,4,2,0,0,6,2,6,0,0,6,2,6,0,0,2,4,2,*[0]*7,6,2,6,0,0,8,6,8,0,0,8,6,8,0,5,1,7,1],[1,8,8,6,5,8,4,4,8,0,8,4,4,8,0,6,8,8,6,*[0]*6,2,6,6,2,0,6,8,8,6,0,6,8,8,6,0,2,6,6,2,*[0]*6,6,8,8,6,0,8,4,4,8,0,8,4,4,8,5,6,8,8,1],[1,9,6,4,1,3,2,8,2,8,8,2,8,2,8,6,4,6,4,6,*[0]*5,2,8,2,8,2,6,4,6,4,6,6,4,6,4,6,2,8,2,8,2,*[0]*5,6,4,6,4,6,8,2,8,2,8,8,2,8,2,3,1,4,6,9,1],[1,0,5,0,5,4,5,*[0]*3,6,*[0]*4,4,*[0]*4,6,*[0]*4,2,*[0]*4,8,*[0]*4,2,*[0]*4,8,*[0]*4,2,*[0]*4,6,*[0]*4,4,*[0]*4,6,*[0]*3,5,4,5,0,5,0,1],[1,1,*[5]*3,9,9,5,0,0,6,6,*[0]*3,4,4,*[0]*3,6,6,*[0]*3,2,2,*[0]*3,8,8,*[0]*3,2,2,*[0]*3,8,8,*[0]*3,2,2,*[0]*3,6,6,*[0]*3,4,4,*[0]*3,6,6,0,0,5,9,9,*[5]*3,1,1],[1,2,6,0,0,4,8,4,5,0,6,2,6,0,0,4,8,4,0,0,6,2,6,0,0,2,4,2,0,0,8,6,8,0,0,2,4,2,0,0,8,6,8,0,0,2,4,2,0,0,6,2,6,0,0,4,8,4,0,0,6,2,6,0,5,4,8,4,0,0,6,2,1],[1,3,8,6,0,4,2,2,9,5,6,8,8,6,0,4,2,2,4,0,6,8,8,6,0,2,6,6,2,0,8,4,4,8,0,2,6,6,2,0,8,4,4,8,0,2,6,6,2,0,6,8,8,6,0,4,2,2,4,0,6,8,8,6,5,9,2,2,4,0,6,8,3,1],[1,4,1,4,6,4,6,4,1,4,1,*[4,6]*7,*[2,8]*12,2,*[6,4]*7,1,4,1,4,6,4,6,4,1,4,1],[1,*[5]*3,*[0]*4,*[5]*4,*[0]*13,8,*[0]*24,8,*[0]*13,*[5]*4,*[0]*4,*[5]*3,1],[1,6,*[0,0,5,0]*3,*[0]*11,8,8,*[0]*23,8,8,*[0]*12,5,*[0]*3,5,*[0]*3,5,0,0,6,1],[1,7,6,*[0,5,5,0]*3,*[0]*10,8,6,8,*[0]*22,8,6,8,*[0]*11,5,5,0,0,5,5,0,0,5,5,0,6,7,1],[1,8,3,6,*[5,0]*6,*[0]*9,8,4,4,8,*[0]*21,8,4,4,8,*[0]*10,*[5,0]*5,5,6,3,8,1],[1,9,1,9,1,*[5]*11,*[0]*9,8,2,8,2,8,*[0]*20,8,2,8,2,8,*[0]*9,*[5]*11,1,9,1,9,1],[1,*[0]*4,6,*[0]*10,5,*[0]*8,8,*[0]*4,8,*[0]*19,8,*[0]*4,8,*[0]*8,5,*[0]*10,6,*[0]*4,1],[1,1,*[0]*3,6,6,*[0]*9,5,5,*[0]*7,8,8,*[0]*3,8,8,*[0]*18,8,8,*[0]*3,8,8,*[0]*7,5,5,*[0]*9,6,6,*[0]*3,1,1],[1,2,1,0,0,6,2,6,*[0]*8,5,0,5,*[0]*6,8,6,8,0,0,8,6,8,*[0]*17,8,6,8,0,0,8,6,8,*[0]*6,5,0,5,*[0]*8,6,2,6,0,0,1,2,1],[1,3,3,1,0,6,8,8,6,*[0]*7,*[5]*4,*[0]*5,8,4,4,8,0,8,4,4,8,*[0]*16,8,4,4,8,0,8,4,4,8,*[0]*5,*[5]*4,*[0]*7,6,8,8,6,0,1,3,3,1],[1,4,6,4,1,6,4,6,4,6,*[0]*6,5,*[0]*3,5,*[0]*4,8,2,8,2,8,8,2,8,2,8,*[0]*15,8,2,8,2,8,8,2,8,2,8,*[0]*4,5,*[0]*3,5,*[0]*6,6,4,6,4,6,1,4,6,4,1],[1,5,0,0,5,7,*[0]*4,6,*[0]*5,5,5,0,0,5,5,*[0]*3,8,*[0]*4,6,*[0]*4,8,*[0]*14,8,*[0]*4,6,*[0]*4,8,*[0]*3,5,5,0,0,5,5,*[0]*5,6,*[0]*4,7,5,0,0,5,1],[1,6,5,0,5,2,7,*[0]*3,6,6,*[0]*4,*[5,0]*4,0,8,8,*[0]*3,6,6,*[0]*3,8,8,*[0]*13,8,8,*[0]*3,6,6,*[0]*3,8,8,0,*[0,5]*4,*[0]*4,6,6,*[0]*3,7,2,5,0,5,6,1],[1,7,1,5,5,7,9,7,0,0,6,2,6,*[0]*3,*[5]*8,0,8,6,8,0,0,6,2,6,0,0,8,6,8,*[0]*12,8,6,8,0,0,6,2,6,0,0,8,6,8,0,*[5]*8,*[0]*3,6,2,6,0,0,7,9,7,5,5,1,7,1],[1,8,8,6,0,2,6,6,7,0,6,8,8,6,0,0,5,*[0]*7,5,8,4,4,8,0,6,8,8,6,0,8,4,4,8,*[0]*11,8,4,4,8,0,6,8,8,6,0,8,4,4,8,5,*[0]*7,5,0,0,6,8,8,6,0,7,6,6,2,0,6,8,8,1],[1,9,6,4,6,2,8,2,3,7,6,4,6,4,6,0,5,5,*[0]*6,5,3,2,8,2,8,6,4,6,4,6,8,2,8,2,8,*[0]*10,8,2,8,2,8,6,4,6,4,6,8,2,8,2,3,5,*[0]*6,5,5,0,6,4,6,4,6,7,3,2,8,2,6,4,6,9,1],[1,0,5,0,0,8,0,0,5,0,3,*[0]*4,6,5,0,5,*[0]*5,5,8,5,*[0]*3,4,*[0]*4,4,*[0]*4,8,*[0]*9,8,*[0]*4,4,*[0]*4,4,*[0]*3,5,8,5,*[0]*5,5,0,5,6,*[0]*4,3,0,5,0,0,8,0,0,5,0,1],[1,1,5,5,0,8,8,0,5,5,3,3,*[0]*3,6,1,*[5]*3,*[0]*4,5,3,3,5,0,0,4,4,*[0]*3,4,4,*[0]*3,8,8,*[0]*8,8,8,*[0]*3,4,4,*[0]*3,4,4,0,0,5,3,3,5,*[0]*4,*[5]*3,1,6,*[0]*3,3,3,5,5,0,8,8,0,5,5,1,1],[1,2,6,0,5,8,6,8,5,0,8,6,3,0,0,6,7,6,0,0,5,*[0]*3,5,8,6,8,5,0,4,8,4,0,0,4,8,4,0,0,8,6,8,*[0]*7,8,6,8,0,0,4,8,4,0,0,4,8,4,0,5,8,6,8,5,*[0]*3,5,0,0,6,7,6,0,0,3,6,8,0,5,8,6,8,5,0,6,2,1],[1,3,8,6,5,3,4,4,3,5,8,4,9,3,0,6,3,3,6,0,5,5,0,0,5,3,4,4,3,5,4,2,2,4,0,4,2,2,4,0,8,4,4,8,*[0]*6,8,4,4,8,0,4,2,2,4,0,4,2,2,4,5,3,4,4,3,5,0,0,5,5,0,6,3,3,6,0,3,9,4,8,5,3,4,4,3,5,6,8,3,1],[1,4,1,4,1,8,7,8,7,8,3,2,3,2,3,6,9,6,9,6,5,0,5,0,5,8,7,8,7,8,9,6,4,6,4,4,6,4,6,4,8,2,8,2,8,*[0]*5,8,2,8,2,8,4,6,4,6,4,4,6,4,6,9,8,7,8,7,8,5,0,5,0,5,6,9,6,9,6,3,2,3,2,3,8,7,8,7,8,1,4,1,4,1],[1,*[5]*4,9,*[5]*4,1,*[5]*4,9,*[5]*4,1,*[5]*4,3,*[5]*4,7,5,*[0]*3,8,*[0]*4,2,*[0]*4,8,*[0]*4,8,*[0]*4,2,*[0]*4,8,*[0]*3,5,7,*[5]*4,3,*[5]*4,1,*[5]*4,9,*[5]*4,1,*[5]*4,9,*[5]*4,1],[1,6,*[0]*3,4,4,*[0]*3,6,6,*[0]*3,4,4,*[0]*3,6,6,*[0]*3,8,8,*[0]*3,2,2,5,0,0,8,8,*[0]*3,2,2,*[0]*3,8,8,*[0]*3,8,8,*[0]*3,2,2,*[0]*3,8,8,0,0,5,2,2,*[0]*3,8,8,*[0]*3,6,6,*[0]*3,4,4,*[0]*3,6,6,*[0]*3,4,4,*[0]*3,6,1],[1,7,6,0,0,4,8,4,0,0,6,2,6,0,0,4,8,4,0,0,6,2,6,0,0,8,6,8,0,0,2,4,7,5,0,8,6,8,0,0,2,4,2,0,0,8,6,8,0,0,8,6,8,0,0,2,4,2,0,0,8,6,8,0,5,7,4,2,0,0,8,6,8,0,0,6,2,6,0,0,4,8,4,0,0,6,2,6,0,0,4,8,4,0,0,6,7,1],[1,8,3,6,0,4,2,2,4,0,6,8,8,6,0,4,2,2,4,0,6,8,8,6,0,8,4,4,8,0,2,6,1,2,5,8,4,4,8,0,2,6,6,2,0,8,4,4,8,0,8,4,4,8,0,2,6,6,2,0,8,4,4,8,5,2,1,6,2,0,8,4,4,8,0,6,8,8,6,0,4,2,2,4,0,6,8,8,6,0,4,2,2,4,0,6,3,8,1]]
class Solution:
    def hasSameDigits(self, s: str) -> bool:
        s1 = s2 = 0
        for binom, (a, b) in zip(tab[len(s) - 2], pairwise(map(int, s))):
            s1 += binom * a
            s2 += binom * b
        return (s1 - s2) % 10 == 0
```
['Python3']