Check If Digits Are Equal in String After Operations II
Complexity
Time complexity: O(N)

Space complexity: O(1)
Code


# Complexity
- Time complexity: O(N)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(1)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```python []
class Solution(object):
    def hasSameDigits(self, s):
        """
        :type s: str
        :rtype: bool
        """
        def is_valid(mod):
            def decompose(x, mod):
                cnt = 0
                while x > 1 and x % mod == 0:
                    x //= mod
                    cnt += 1
                return x, cnt

            res = cnt = 0  
            curr = 1       
            n = len(s) - 1 

            for i in xrange(n):
                if cnt == 0:
                    res = (res + curr * (ord(s[i]) - ord(s[i + 1]))) % mod

                x, c = decompose(n - i - 1, mod) 
                curr = (curr * x) % mod
                cnt += c

                x, c = decompose(i + 1, mod)  
                curr = (curr * pow(x, mod - 2, mod)) % mod  
                cnt -= c

            return res == 0  

        return is_valid(2) and is_valid(5)
```
['Math', 'String', 'Combinatorics', 'Number Theory', 'Python']