Python Binary Search for M inverse: 1/M
Most posts are using pattern-finding method, which is excellent and fast (~40 ms)\nHere I provide a Binary Search solution, which is a bit slow(~380 ms) but pre
Most posts are using pattern-finding method, which is excellent and fast (~40 ms)\nHere I provide a Binary Search solution, which is a bit slow(~380 ms) but pretty straightforward to understand.\n\nBasically, we are required to find biggest M, satisfying s2x(n2xM) is subsequence of s1xn1.\nsuppose we find M=10, then we know that for M=9,8,7,6...the subsequence condition should also hold. Therefore, we could use Binary Search to find M.\n\nHowever, for most tranditional binary search pattern (lo=mid+1 & hi=mid), they are not directly useable for upper-bound-finding case like this problem. ```we need to convert upper-bound-finding problem to be a lower-bound-finding problem```. Thus, the solution is: \nwe use Binary Search algorithm to find the ```lower-bound of 1/M```, which ``corresponds to upper-bound of M``.\n\nThe following is the explanation for function issubseq(s2, n2, s1, n1).\ninitially, we count the number of s1 for ```matching single s2```, we call it ```s1_used```, usually there would be a half-used s1 for matching s2\'s tail, which is between ```best case``` and ```worst case```.\n\nso the ```best case``` would be ```s1_used s1``` cover ```single s2```, and  ```n2*s1_used s1``` cover ```n2 s2```\nthe ```worst case``` would be ```(s1_used+1) s1``` cover ```single s2```, and ```n2*(s1_used+1) s1``` cover ```n2 s2```.\n\nthus, if ```n1 <  n2*s1_used``` for best case, return ```False```.\nif ```n1 >=  n2*(s1_used+1)``` for worst case, return ```True```.\nfinally, the hard part is what if n1 is between best case and worst case?\n\nIn this situation, we will try to match another single s2 again from the end index of previous matching, until we meet the above two extreme conditions or ```there is no half-used s1 when a full s2-matching is done```.\n\n```\nclass Solution:\n    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n        \n        def divide_gcd(n1, n2):\n            m, n = n1, n2\n            while m % n:\n                m, n = n, m % n\n            return n1 // n, n2 // n\n        \n        def issubseq(s2, n2, s1, n1):  # return True/False s2*n2 is the subsequence of s1*n1\n            s2_used = 0\n            s1_used, s1_sidx = 0, 0\n            while True:\n                for ch in s2:\n                    j = s1.find(ch, s1_sidx)\n                    if j == -1:\n                        s1_used += 1\n                        j = s1.find(ch, 0)\n                    s1_sidx = j + 1\n                s2_used += 1\n                if s1.find(s2[0], s1_sidx) == -1:\n                    s1_used += 1\n                    return s1_used * n2 <= s2_used * n1  # rewrite the original condition: s1_used / s2_used >= n2 / n1\n                if s1_used * n2 >= s2_used * n1:\n                    return False\n                if s1_used * n2 + n2 <= s2_used * n1:\n                    return True\n        \n        if not set(s2).issubset(set(s1)):\n            return 0\n        if len(s1) * n1 < len(s2) * n2:\n            return 0\n        \n        n1, n2 = divide_gcd(n1, n2)\n        lo, hi = (len(s2) * n2) / (len(s1) * n1), 10**5\n        while lo + 1e-11 < hi:\n            mid = (lo + hi) / 2\n            if issubseq(s2, n2*(int(1/mid)+1), s1, n1):\n                hi = mid\n            else:\n                lo = mid\n        return int(1/lo)\n```
[]