Very tricky one

767. Reorganize String

From stefan

class Solution:
    def reorganizeString(self, S: str) -> str:
        a = sorted(sorted(S), key=S.count)
        h = len(a)//2
        a[::2], a[1::2] = a[h:], a[:h]
        return ''.join(a)*(a[-1:]!=a[-2:-1])

A more standard way to solve this problem from here

The idea is to build a max heap with freq. count
a) At each step, we choose the element with highest freq (a, b) where b is the element, to append to result.
b) Now that b is chosen. We cant choose b for the next loop. So we dont add b with decremented value count immediately into the heap. Rather we store it in prev_a, prev_b variables.
c) Before we update our prev_a, prev_b variables as mentioned in step 2, we know that whatever prev_a, prev_b contains, has become eligible for next loop selection. so we add that back in the heap.

In essence,

• at each step, we make the currently added one ineligible for next step, by not adding it to the heap
• at each step, we make the previously added one eligible for next step, by adding it back to the heap

def reorganizeString(self, S):
        res, c = [], Counter(S)
        pq = [(-value,key) for key,value in c.items()]
        heapq.heapify(pq)
        p_a, p_b = 0, ''
        while pq:
            a, b = heapq.heappop(pq)
            res += [b]
            if p_a < 0:
                heapq.heappush(pq, (p_a, p_b))
            a += 1
            p_a, p_b = a, b
        res = ''.join(res)
        if len(res) != len(S): return ""
        return res

91. Decode Ways

from functools import lru_cache
class Solution:
    def numDecodings(self, s: str) -> int:
        a = string.ascii_uppercase
        d = {str(i):c for i,c in enumerate(a, 1)}
       
        @lru_cache(None)
        def dfs(k):
            if k==len(s):return 1
            w = ""
            res = 0
            for i in range(k, len(s)):
                w += s[i]
                if w in d:
                    this_res =dfs(i+1)
                    res+=this_res
                else:
                    break
            return res
        return dfs(0)

Time complexity of above code is O(n)

class Solution:
    def numDecodings(self, s: str) -> int:
        dp = [0]*(len(s)+1)
        dp[0] = 1
        for i in range(len(s)):
            this_one = 0
            if s[i]!='0':dp[i+1] +=dp[i]
            if i>=1 and 10<=int(s[i-1:i+1])<=26:dp[i+1]+=dp[i-1]
        #print(dp)
        return dp[-1]

227. Basic Calculator II

class Solution:
    def calculate(self, s: str) -> int:
        s = s.replace(" ","")
        num, stack, prev_operation = 0, [], '+'
        # 234
        # stack = [234]
        for i, c in enumerate(s):
            if c.isdigit():
                num = 10*num+int(c)
            if c in '+-*/' or i==len(s)-1:
                if prev_operation=='+':
                    stack.append(num)
                elif prev_operation =='-':
                    stack.append(-num)
                elif prev_operation=='*':
                    stack.append(stack.pop()*num)
                else:
                    stack.append(int(stack.pop()/num))
                num = 0
                prev_operation = c
        return sum(stack)