Useful python alg

counting number of pairs whose diff is < target

we can use two pointer and look at my explanation
https://velog.io/@whitehousechef/Leetcode-719.-Find-K-th-Smallest-Pair-Distance

def check(guess):
            total=0
            left=0
            for right in range(len(nums)):
                while nums[right]-nums[left]>guess and left<right:
                    left+=1
                total+=right-left
            return total

generating palindrome

we are generating palindromes each time function is called. When i becomes 10 digits is 2 and from 0 to 10, we make it like 11 22 33 etc. When digits is even like 10, we can just split exactly into half. But when digits is odd like 120, we need to slicing the last character 0 and just get 12 and reverse it.

        def generatePalindrome():
            for i in range(1,10):
                yield i

            digits=1

            while True:
                digits+=1
                half = (digits+1)//2
                start = 10**(half-1)
                end = 10**half
                for i in range(start,end):
                    s=str(i)

                    if digits%2==0:
                        right_part=s[::-1]
                        palin = s+right_part
                    else:
                        right_part=s[-2::-1]
                        palin = s+right_part
                    yield int(palin)

see if subsequence appears k times in an original string

we use iter() and clever logic is, if subsequence (cur) *k can be seen in the original string, that is true. We dont have to see if cur explicitly repeats k times but if we just multiply by k times, and use iter() to iterate through each character in the original string, that does the trick

def check(s, t):  # s = subsequence, t = original string
    t = iter(t)
    return all(c in t for c in s)
    
    #without list comprehension
    def check_explicit_loop(s, t):
        t = iter(t)
        for c in s:
            if c not in t:
                return False
        return True


# Call as: check(cur*k, s)

Count number of subsequences that must include nums[0]

for e.g. [3,5,6], we can make 4 subsequences. [3],[3,5],[3,5,6], [3,6].
The formula is 2(right pointer- left pointer)= 22= 4.

This cuz
from POV of nums[0] (leftmost val), we have option whether to take value of nums[1], nums[2], all the way to nums[r]. These range of options is right-left.

Then, for each value, we have option whether to take this value or not, which is 2 options. That is why fromula is 2**(r-l).

Look at this:
https://velog.io/@whitehousechef/Leetcode-1498.-Number-of-Subsequences-That-Satisfy-the-Given-Sum-Condition

Permu and Combi template

https://velog.io/@whitehousechef/Neetcode-Permutations