LeetCode 459. Repeated Substring Pattern

Question: https://leetcode.com/problems/repeated-substring-pattern/

This is the first string related question. Lots of the String algorithm questions look innocent, but when you dig into some of these questions, it takes some genius to come up with really smart and efficient algorithm. I remember learning KMP (knuth morris pratt) algorithm in class, and it really takes me a while to first understand what the algorithm is doing and then convince myself that it works. This problem is not as hard or as complicated as the KMP algorithm. The second solution is indeed quite smart.

My initial idea is that when you keep on rotating a valid repeated substring, you will eventually get back the same string. s[i:] + s[:i] is a pythonic way to rotate a string. It is easier to understand what rotating a string means. Let's say we have "abc", we shift the string to the left by one, we will have "bca" where "a" got pushed around to the end. Shift one more time, we have "cab".

class Solution(object):
    def repeatedSubstringPattern(self, s):
        """
        :type s: str
        :rtype: bool
        """
        n = len(s)
        ans = False
        if n == 1:
            ans = False
        else:
            for i in range(1, n):
                if s[i] == s[0]:
                    ans = (s[i:] + s[:i]) == s
                    if ans:
                        break
        return ans

Here comes the smart algorithm:

class Solution(object):
    def repeatedSubstringPattern(self, s):
        """
        :type s: str
        :rtype: bool
        """

        return s in s[1:] + s[:-1]

Why does it work? Consider the case for a valid repeated substring. Suppose the string has a repeating pattern "abc", and it repeated twice. The string is "abcabc" then when we form the string by concatenating the substring that cut off the first character and the substring that cut off the last character. We form the string "bc[abcabc]ab", we see the original string is in there as bolded. By cutting one character off the pattern, we were taking away one repeating pattern away from the original string. However, when we concatenate the substring that takes the first character away with the substring with last charater cutoff, we will get the back the original string embedded in this new string.

LeetCode 925. Long Pressed Name

Question: https://leetcode.com/problems/long-pressed-name/

As a mac user, I know lots of people had issues with the butterfly keyboard. Many people complained that when a key is hit, it can repeat itself multiple time causing great pain when typing. Now this duplicate character problem can be alleviated (to the smallest degree) with the algorithm used in this question. We are checking if a typed word is a long pressed version of the word that we intended to type. While checking is not correcting, it is still a step forward. A follow-up question will be warranted to correct words like the gramma checking software (will do an algo question on this).

The general idea is to count the number of characters in groups. A valid long pressed version of the word will the same clusters of characters as in the name. For instance, for the input name="xexe", typed= "xxeexeee", we convert these two strings into a count of the characters in the group. "xexe" becomes [1,1,1,1] corresponding to the sequence of clusters [(x,1), (e,1),(x,1), (e,1)]. Similarly, "xxeexeee" will become [2,2,1,3], corresponding to the sequence of cluster [(x,2), (e,2), (x,1),(e,3)]. Once these count sequences are formed, it is obvious that any long-typed version should have a larger count of the character than the original name.

One caveat is in the count of clusters. We are comparing the neighbor two characters to see if they are the same. We can either do i and i+1, or i-1 and i. I have picked the later. In this case, when the two characters are different s[i-1] and s[i], we know the cluster ended at i-1. Count only gets incremented when the two characters are the same. So when we append count to the array, we know we are appending the length of the cluster ended at i-1. Do remember to append count to array after we exit the loop. It is because that the last check we do is for s[n-1] and s[n-2], if they are the same, the count gets incremented, but since the loop exit there, we never reach the append statement. If they are different, then as explained above, we get the count of the cluster ended at n-2, we still need to append the count to the array. Either way, we will need to append the count to the array at the end.

class Solution(object):
    def isLongPressedName(self, name, typed):
        """
        :type name: str
        :type typed: str
        :rtype: bool
        """
        
        def char_counts(s):
            counts = []
            n = len(s)
            if len(s)>=1:
                i = 1
                count = 1
                while i < n:
                    if s[i-1] == s[i]:
                        count += 1
                    else:
                        counts.append(count)
                        count = 1
                    i += 1
                counts.append(count)
            return counts
        
        name_counts = char_counts(name)
        typed_counts = char_counts(typed)
        ans = True
        if len(name_counts) != len(typed_counts):
            ans = False
        else:
            for i, count in enumerate(typed_counts):
                if name_counts[i] > typed_counts[i]:
                    ans = False
                    break
        return ans

LeetCode 169. Majority Element

Question: https://leetcode.com/problems/majority-element/

This is one of those popular questions that have multiple solutions. The easiest to come up with is simply iterate through the array and count the occurrences. The Efficiency of this solution is O(N). This takes 160 ms and 13.3 MB .

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """ 
        counts = {}
        n = len(nums)
        for num in nums:
            if num in counts:
                counts[num] += 1
                if counts[num] > n// 2:
                    break
            else:
                counts[num] = 1
        return num

Every time one encounters an array question, we should always think about whether sorting can help. In this case, once the array is sorted, we know that numbers of the same value are clustered, and we can increment the counter if the number under observation is the same as the previous value, and set the count back to 1 once a new value is encountered. This is O(NlogN) because of the sorting procedure. It takes 160ms and 14.2MB to run. This is rather strange, especially with the larger memory required compared to the count solution above.

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """ 
        n = len(nums)
        if n == 1:
            return nums[0]
        nums = sorted(nums)
        count = 1
        for i, num in enumerate(nums):
            if nums[i] == nums[i+1]:
                count +=1 
            else:
                count = 1
            if count > n//2:
                break
        return num

Now LeetCode's solution page has 6 different ways of solving this. I find the Boyer–Moore majority vote algorithm to be very clever and efficient. It takes only 144 ms and 13.3MB to run. By far the best solution. People can get confused about the definition of majority element. It is defined as any element that has a count greater than n//2, not the element with the largest count! For instance, let's say we have an array [7,7,5,5,1,1,7]. At first glance, it looks like 7 is the majority element. However, this is not true, there is no majority element in this array, because even 7 has only a count of 3, which is equal to 7//2=3, not exceeding n//2! So this array would not satisfy as a valid input to the question. The algorithm works exactly because of this property. The key property is this: when we encounter a tie (count=0) at index k, the majority element in [k:] will be the majority element of the original array. It takes some time to fully digest this. 

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """ 
        count = 0
        candidate = None

        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if num == candidate else -1)

        return candidate

LeetCode 404. Sum of Left Leaves

Question: https://leetcode.com/problems/sum-of-left-leaves/

Unlike the other tree questions, the iterative solution is more intuitive and easier to come up with than the recursive one. The iterative solution is a simple application of Breath First Search (BFS). We just need to insert some code to check if the left node is a leaf when we insert that node back into the queue. The solution runs in 24ms and uses 12.3MB (slower than the recursive solution below, but use less space).

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import deque
class Solution(object):
    def sumOfLeftLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        ans = 0
        q = deque()
        if root:
            q.append(root)
            visited = {}
            while q:
                v = q.popleft()
                if v not in visited:
                    if v.left:
                        if not v.left.left and not v.left.right:
                            ans += v.left.val
                        q.append(v.left)
                    if v.right:
                        q.append(v.right)
                    visited[v] = True
        return ans

The recursive solution is harder to write because we need information that is above the current level. The information we need is if the node under observation is a left leaf. This information cannot be gained without using an auxiliary recursive helper. A recursive helper is simply a wrapper that allows one to append additional information to the function. If we just recursively call the original function sumOfLeftLeaves(root), there is no way we can add any additional information, since the function arguments are fixed. Therefore, we have defined an inner function with the isLeft argument to tell the function of whether the node that we passed is a left child or not. Given this freedom, we now know if the node passed is a left node or not, if it's a left node, then we apply the same logic as it is in the iterative BFS solution, we check if this node is a leaf, if so, we simply add the value to the answer.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def sumOfLeftLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
         def recursive_helper(root, isLeft):
             ans = 0
             if root:
                 if isLeft and (not root.left and not root.right):
                     ans += root.val
                 else:
                     ans += recursive_helper(root.left, True)
                     ans += recursive_helper(root.right, False)
             return ans
            
         return recursive_helper(root, False)
            

Related Question:

• Maximum Binary Tree: https://monkeyinvestment.blogspot.com/2020/03/leetcode-654-maximum-binary-tree.html
• Binary Tree Paths: https://monkeyinvestment.blogspot.com/2020/03/leetcode-257-binary-tree-paths.html

LeetCode 191. Number of 1 Bits (Hamming Weight)

Question: https://leetcode.com/problems/number-of-1-bits

This is an interesting bit manipulation problem. I have come up with two solutions, but the third one is quite out of expectation. Speed comparison between all three solutions is also quite interesting.

1. The below solution is what normal people would come up with when first looking at the problem. We simply find all the bits of a number and increment the count whenever a bit 1 is encountered. The speed and memory usage are 20ms and 12MB. The asymptotic efficiency is O(logN)

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        # Normal People Solution
        count = 0
        while n // 2!=0:
            if n % 2 == 1:
                count += 1
            n //= 2
        if n == 1:
            count += 1
        return count

2. We can also use a 32-bit long mask to pick out one bit at a time and count the bit if it's 1. It's an easy application of the idea that when a number, n,  AND with a number that is an exponential of 2, we will simply pick out the bit of n in the corresponding location. For instance, 5 = 101, when AND with 4=100, we get 101 & 100 = 100 = 4. Speed and memory usage are 20ms and 11.9MB.

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        count = 0
        for i in range(32):
            mask = 2**i
            if (n & mask)==mask:
                count +=1
        return count

Instead of raising 2^i to get the mask, we can also use shift operator like it is below. Shifting a bit to the right simply multiply a number by 2. Surprisingly, there is no improvement in speed and memory: 24 ms and 11.9MB.

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        count = 0
        mask = 1
        for i in range(32):
            if (n & mask)==mask:
                count +=1
            mask <<= 1
        return count

3. Now here comes the most unexpected solution. First of all, what does n&n-1 do? It flips the least significant bit. Why does it flip the least significant bit? Think of a number like 6 = 110. Comparing this to 6-1=5=101. We see that the part to the right of the least significant bit in 6, 110 got subtracted by 1. yielding 101. This is what happened when we subtract 1 from any number n, we are subtracting 1 of the part to the right of the least significant bit leaving the part to the left intact. What happens when we AND n with n-1? We know that the part to the left is intact, because x & x = x. How about the part to the right? well, we know the part to the right will definitely be of the form (100...), let's call this x. Then, x-1 is of the form (011....). Therefore, x&x-1 becomes (00000....)! It is equivalent to flipping the least significant bit from 1 to 0! The algorithm below just keeps on flipping the least significnt bit until it reaches 0. The speed and memory is 16ms and 11.7MB. Faster with lower memory usage!

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """        
        # Superman Solution
        count = 0
        while n != 0:
            n &=n-1
            count += 1
        return count

Related Questions:
Number Complement: https://monkeyinvestment.blogspot.com/2020/03/leetcode-476-number-complement.html

LeetCode 654. Maximum Binary Tree

Questions: https://leetcode.com/problems/maximum-binary-tree/

As it is explained in a previous tree question. A recursive solution to tree problems is much easier to come by. In this case, we just need to find the maximum in the array, and apply the definition of the maximum binary tree as it's described in the question.

A general approach that I took to solve this type of question is to write down the solution to the general case with the minimum size. For example, we will start with len(nums) = 2. In this case, we will have max_pos either in position 0 or 1. Then either our leftTree or rightTree will be empty. Given this thought, you know your base case has to have the case when nums are passed in as an empty list [] with size 0, and there you go, in under 5 minutes, you already solved the problem labeled as medium difficulty. I doubt this question is actually of medium difficulty. I will challenge myself to an alternative way of solving this problem in another time.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def constructMaximumBinaryTree(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        n = len(nums)
        if n == 0:
            return None

        max_pos = 0
        curmax = nums[max_pos]
        for i in range(n):
            if curmax < nums[i]:
                curmax = nums[i]
                max_pos = i
        root = TreeNode(nums[max_pos])
        leftTree = self.constructMaximumBinaryTree(nums[:max_pos])
        rightTree = self.constructMaximumBinaryTree(nums[max_pos+1:])
        root.left = leftTree
        root.right = rightTree
        return root
        

LeeCode 788. Rotated Digits

Question: https://leetcode.com/problems/rotated-digits

The below solution is slow and uses lots of space when compared to other correct solutions submitted to LeetCode. The get_digit process is O(logN), and we have to iterate through all integers up to N, so the overall efficiency is O(NlogN). I would think this already achieves the highest efficiency asymptotically. I will come back to this problem, and see where I got it wrong.

class Solution(object):
    def rotatedDigits(self, N):
        """
        :type N: int
        :rtype: int
        """
        rotation_map = {0:0, 1:1, 8:8, 2:5, 5:2, 6:9, 9:6}
        
        def get_digits(k):
            digits = []
            while k // 10!=0:
                digits.append(k % 10)
                k //= 10
            digits.append(k % 10)
            return digits
        
        count = 0
        for i in range(1, N+1):
            digits = get_digits(i)
            all_same = True
            for digit in digits:
                if digit not in rotation_map:
                    all_same=True # Setting this to true force the later check to fail and 
                    # avoid counting this digit
                    break
                elif digit not in (0,1,8):
                    all_same = False
                else:
                    continue
                    
            if not all_same:
                count += 1
        return count

LeetCode 119. Pascal's Triangle II

Question: https://leetcode.com/problems/pascals-triangle-ii/

This is a classic question, but I have not done this problem before. Personally, I like solving math-related algorithm questions, like those in the Euler's Project. This is not quite the kind of math question. Nonetheless, Pascal is one of the greatest mathematicians. So a question bearing his name would be worth doing.  The idea is just to apply the definition of a pascal triangle but using a fixed-size array. Given a rowIndex, we will know the size of the array. For instance, rowIndex=3, gives us [1,3,3,1] an array of size 4. Therefore, given rowIndex, we simply initialize a size (rowIndex+1) array. The key idea is that an array of this size would be sufficient enough to store all the previous solutions for smaller rowIndex. We will keep using this same array to store the solutions when the input = rowIndex-1. For instance, we will start with [1,1,1,1]. Starting from the rowIndex =2, we will have a = 1, b=1 and c = a+b=2 and insert 2 into the correct position yielding [1,2,1,1]. In the next iteration, we will calculate the rowIndex=3. The initial array is [1,2,1,1] , where the subarray [1,2,1] is the solution to rowIndex=2, summing from left to right will yield [1,3,3,1], as desired. A small detail to pay attention to is the assignment of a,b for the next iteration. Since we will be assigning ans[j+1] to the new value c=a+b, we will lose the reference to the next a, therefore, we will do the assignment after we have moved a, b pointers forward for the next iteration.

class Solution(object):
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """
        if rowIndex == 0:
            return [1]
        elif rowIndex == 1:
            return [1,1]
        else:
            ans = [1 for _ in range(rowIndex+1)]
            for i in range(1, rowIndex):
                a = ans[0]
                b = ans[1]
                for j in range(i):
                    c = a + b
                    a, b = b, ans[j+2]
                    ans[j+1] = c
            return ans

LeetCode 257. Binary Tree Paths

Question: https://leetcode.com/problems/binary-tree-paths/

For those who are curious, I am following this sheet of Leetcode questions sorted by difficulty starting from the easiest to the hardest. I find most of the questions previously posted are too simple. I am skipping ahead to some harder ones. The question today is not as difficult, but just like the matrix iteration problem. It provides a skeleton in solving many of the tree problems.

I have solved the question both recursively and iteratively. Personally, I find the recursive solution to be more intuitive. For any recursive solution, we just need to imagine if we have had the answer to the subproblem, what should we do to get the solution. In this case, once we have the paths of the left subtree and right subtree, we simply insert our path node value to the beginning of the paths. The only caveat is to pay close attention to corner cases. Ask yourself, what if the root is NULL? what if the root has no left or right children? Once these corner cases are answered, usually for the easier tree-based questions, the solution should be quite obvious.

The iterative solution is based on the Depth First Search (DFS). This is a general way of traversing a graph (note tree is just a graph). DFS works well in this case, because, it goes all the way to the leaves, and once we reach a leaf, we simply append the path recorded so far to the paths list. The trick here is how one keep track of the path along the way. In python, we can simply use Tuple to store that path along with the node when we push the node to the stack. Whenever we pop that node out, we have the path that leading up to that node. Pushing some additional value along with the node is a general technique for many tree-based questions. For example, this can be used to find the level of a tree for any node as well.

I believe breadth first search (BFS) should work as well, but the code would not be as clean.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        # Recursive Solution
#         paths = []
#         if root:
#             if not root.left and not root.right:
#                 paths.append(str(root.val))
#             if root.left:
#                 leftPaths = self.binaryTreePaths(root.left)
#                 for leftPath in leftPaths:
#                     paths.append("{}->{}".format(root.val, leftPath))
#             if root.right:
#                 rightPaths = self.binaryTreePaths(root.right)
#                 for rightPath in rightPaths:
#                     paths.append("{}->{}".format(root.val, rightPath))            
#         return paths

        # Iterative Solution
        stack = []
        paths = []
        if root:
            stack.append((root, "{}".format(root.val)))
            visited = {}
            while stack:
                v, path = stack.pop()
                if v not in visited:
                    if not v.right and not v.left: # We have reached a leaf
                        paths.append(path)
                    if v.right:
                        stack.append((v.right, "{}->{}".format(path, v.right.val)))
                    if v.left:
                        stack.append((v.left, "{}->{}".format(path, v.left.val)))
                    visited[v] = True
        return paths          

Related Questions:
Binary Tree Paths: https://monkeyinvestment.blogspot.com/2020/03/leetcode-257-binary-tree-paths.html

LeetCode 463. Island Perimeter

Question: https://leetcode.com/problems/island-perimeter/

This easy question gives a skeleton for iterating a matrix and checking for boundary conditions.

class Solution(object):
    def islandPerimeter(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        nrows = len(grid)
        ncols = len(grid[0])
        counts = 0

        for i in range(nrows):
            for j in range(ncols):
                if grid[i][j] == 1:
                    if i-1<0:
                        counts += 1
                    else:
                        if grid[i-1][j] == 0:
                            counts += 1
                    if i+1>=nrows:
                        counts += 1
                    else:
                        if grid[i+1][j] == 0:
                            counts += 1
                    if j-1<0:
                        counts += 1
                    else:
                        if grid[i][j-1] == 0:
                            counts += 1
                    if j+1>=ncols:
                        counts += 1
                    else:
                        if grid[i][j+1] == 0:
                            counts += 1
        return counts

                   

LeetCode 942. DI String Match

Question: https://leetcode.com/problems/di-string-match/

This one is by far the most interesting question, and I have spent quite some time on it. Once you saw the solution, it becomes obvious. The implementation takes me quite a while to get it right.

The overall idea is to be greedy. When encountered "I", increase as little as possible, and decrease as little as possible for "D".

Why this works? Let's look at an example "DDI". Imagine, we are inserting spaces in between characters, like "_D_D_I_". We are going to pick numbers between [0, 3] to insert into the underscored positions. When we encounter the very first character in S, the decision is easy, pick n when "D" encountered, and 0 for "I". Intuitively, this leaves the most room for later manipulation. In this case, we pick 3 for the first position. Now, the newMax = 2, and min is still 0. The imaginary string now becomes "3D_D_I_".  Moving on to the second character "D", by being greedy, we simply put curMax=2 into the second underscore, because again it leaves the most room available for later manipulation and satisfies the first character "D" by the virtue of us choosing 3 (the previous max) as our choice. So this is the essence of the greedy algo, previous choices make sure we are on the optimal path towards the solution. Continue to the 3rd character "I", we now put in the curMin=0, leaving enough room for later manipulation, and satisfying previous "D" condition. Finally, we settle with 1, because that is the only number left to pick.

A general proof of greedy algorithm can be found here: https://cs.stackexchange.com/questions/59964/how-to-prove-greedy-algorithm-is-correct

The formality can make people lose their minds, but it is worthwhile reading this answer from SO.

class Solution(object):
    def diStringMatch(self, S):
        """
        :type S: str
        :rtype: List[int]
        """
        n = len(S)
        ans = []
        curmax, curmin = n, 0
      
        for char in S:
            if char == "I":
                ans.append(curmin)
                curmin +=1
            else:
                ans.append(curmax)
                curmax -= 1
        return ans + [curmax]

LeetCode 476. Number Complement

Question: https://leetcode.com/problems/number-complement/

I love bit manipulation problems. Some of the tricks are just like magic. XOR is one of those magic operators that when used properly can yield surprisingly concise solutions. A couple of quick usages of XOR:

• XOR a number with itself odd number of times the result is number itself.
• XOR a number even number of times with itself, the result is 0.
• XOR with 0 is always the number itself.
• XOR a number say (5=110) with (111) will flip the bits and yield (1=001).

The complement of a number is exactly a direct application of the last bullet point. We just need to XOR the number with the maximum number that can be formed using the same number of bits. So the task is just to find the number of bits the input number has and construct that number in a decimal form that will be XORed with the input number to get the complement. Getting the binary representation of a number is a fairly standard procedure that everyone should know.

class Solution(object):
    def findComplement(self, num):
        """
        :type num: int
        :rtype: int
        """
        binmax = 0
        i = 0
        ans = num
        while num//2 !=0:
            binmax += 2**i
            i += 1
            num //=2
        binmax += 2**i
        return ans ^ binmax

LeetCode 206. Reverse Linked List

Question: https://leetcode.com/problems/reverse-linked-list/

This is such a classic question. I have coded both the recursive and iterative solutions. Linked List can be quite tricky. This reversing the list question is quite good of a demonstration of this. Both of my solutions work, but they are not efficient. I think it will be helpful for others and myself to describe how I come up with the solutions.

The recursive solution is easier to think about. We just need to reverse the list starting after the head, and once the head of the sublist is returned from the recursive call, we iterate that sublist till the last element is reached, and setting that element's next to the head of the original list. The only caveat is to remember setting the head's next to None at the end.

The iterative solution is a bit trickier. If we only maintain 2 points, whenever we assign one of the pointer's next to the other pointer, we lose the reference to the next of the pointer after assignment. This can be solved by maintaining 3 pointers and kept moving forward one step at a time for the 3 pointers. We will keep on moving the points until the middle of the 3 pointers points to the NULL of the last element's next, and simply return the start pointer as the head of the reversed list. My solution is ugly because I need to check for if mid is None inside the while loop. Because when mid already reached the last element's next, which is None, any reference to mid's next will throw exception. Therefore, I am doing that check and essentially breaking out of the while loop.

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # Recursive
        # if not head:
        #     return None
        # if head.next:
        #     tmp = self.reverseList(head.next)
        #     cur = tmp
        #     while cur.next:
        #         cur = cur.next
        #     head.next = None
        #     cur.next = head
        #     return tmp
        # else:
        #     return head
        
        # Iterative
        if not head or not head.next:
            return head    
        i = head
        mid = head.next
        j = mid.next
        idx = 0
        while mid:
            mid.next = i
            if idx == 0:
                i.next = None
            i = mid
            mid = j
            if mid:
                j = mid.next
            idx += 1
        return i
        

LeetCode 1309. Decrypt String from Alphabet to Integer Mapping

Question: https://leetcode.com/problems/decrypt-string-from-alphabet-to-integer-mapping/
Easy Question Again. Since the indicator for a change in character mapping comes from the end with "#", we will need to iterate from behind. One thing to be careful is with the indexing when getting the substring from the input string. First of all, the number of characters extracted from any index pairs such as s[i, i+k] will yield back i+k-i = k characters. So s[i-2:i] gives back 2 characters, exactly what we want. Secondly, s[i-2:i] will include s[i-2] character and exclude s[i]. Just try to avoid these common mistakes, then we are good to go!

class Solution(object):
    def freqAlphabets(self, s):
        """
        :type s: str
        :rtype: str
        """
        ans = []
        char_map = {}
        atoi = ord("a")
        for i in range(1, 27):
            curchar = chr(atoi+i-1)
            char_map["{}".format(i)] = curchar
            
        n = len(s)
        i = n-1
        while i >= 0:
            if s[i] == "#":
                print(i-2, i)
                ans.append(char_map[s[i-2:i]])
                i -= 3
            else:
                ans.append(char_map[s[i]])
                i -= 1
        return "".join(reversed(ans))

LeetCode 1304. Find N Unique Integers Sum up to Zero

Question: https://leetcode.com/problems/find-n-unique-integers-sum-up-to-zero/

I am working my way to harder questions. These easy questions are indeed quite easy, although I almost make mistakes on the first run. The mistake was with the range indexing. For even numbers, I will need to use i+1 instead of i. However, the idea for the solution to these easy questions is quite easy to come by indeed.

class Solution(object):
    def sumZero(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        ans = []
        if n % 2 == 0:
            for i in range(n//2):
                ans.append(i+1)
                ans.append(-(i+1))
        else:
            for i in range(1, n//2+1):
                ans.append(i)
                ans.append(-i)
            ans.append(0)
        return ans

LeetCode 409. Longest Palindrome

Question: https://leetcode.com/problems/longest-palindrome/

The question is quite easy, and the only caveat when solving this problem is to remember adding back 1 to the answer when we encountered any character with an odd number of occurrences.  For any palindrome, we can add that one character to the middle of the palindrome and still get back a palindrome.

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: int
        """
        count = {}
        for i, char in enumerate(s):
            if char in count:
                count[char] += 1
            else:
                count[char] = 1
        ans = 0
        has_odd = False
        for char, k in count.items():
            if k % 2 == 0:
                ans += k
            else: # For those chars with odd number of occurences, we can take an even number of the chars and add them to the palindrome.
                has_odd = True
                ans += k-1
        if has_odd:
            ans += 1
        return ans