[LeetCode] 893. Groups of Special-Equivalent Strings

 Problem : https://leetcode.com/problems/groups-of-special-equivalent-strings/

Because one character on odd position can be unlimitedly swapped with character on another odd position, the order of characters on odd position does not matter. Same to characters on even position. Two words are special-equivalent when they have same set of characters on odd positions and same set of characters on even positions.

class Solution {
    public int numSpecialEquivGroups(String[] words) {
        Set<String> group = new HashSet<>();
        
        for (String w: words) {
            group.add(keyOf(w));
        }
        
        return group.size();
    }
    
    String keyOf(String word) {
        int[] countOdd = new int[26];
        int[] countEven = new int[26];
        
        for (int i = 0; i < word.length(); i++) {
            if ((i & 1) == 1) {
                // odd position
                countOdd[word.charAt(i) - 'a'] += 1;
            } else {
                // even position
                countEven[word.charAt(i) - 'a'] += 1;
            }
        }
        
        StringBuilder sb = new StringBuilder();
        sb.append(Arrays.toString(countOdd));
        sb.append("-");
        sb.append(Arrays.toString(countEven));
       
        return sb.toString();
    }
}

[LeetCode] 1711. Count Good Meals

 Problem : https://leetcode.com/problems/count-good-meals/

This problem is like an enhanced 2sum problem. The only difference is, the 'target' number is not explicitly given.

class Solution:
    def countPairs(self, deliciousness: List[int]) -> int:
        M = 10 ** 9 + 7
        result = 0
        seen = defaultdict(int)
        
        # sort the numbers first
        # for one given number there is no larger number before it.
        deliciousness.sort()
        
        for n in deliciousness:
            # the maximum sum of 'n' is n + n
            # try every power of two less than n + n
            target = 1
            while target <= n + n:
                result += seen[target - n]
                result %= M
                target *= 2
            
            # increase the counter of n
            seen[n] += 1
        
        return result

[LeetCode] 781. Rabbits in Forest

 Problem : https://leetcode.com/problems/rabbits-in-forest/

Remember the last rabbit answered the same values. Then count rabbits must be in different colors.

class Solution:
    def numRabbits(self, answers: List[int]) -> int:
        
        total = 0
        seen = defaultdict(int)
        
        for n in answers:
            if n == 0:
                # encounter a single rabbit of this color
                total += 1
            else:
                if seen[n+1]:
                    # encounter rabbit with same color
                    seen[n+1] -= 1
                else:
                    # encounter rabbit with different color
                    seen[n+1] += n
                    total += n+1
                    
        return total

Another math solution:

Firstly count number of rabbits anwsered the same values. For example, M rabbits answered N. Then there must be M // (N+1) group of rabbits with same color. Each group has N+1 rabbits. Additionally, there must be another group of N+1 rabbits if M % (N+1) > 0.

class Solution:
    def numRabbits(self, answers: List[int]) -> int:
        
        total = 0
        count = Counter(answers)
        
        for n, m in count.items():
            total += m // (n+1) * (n+1)
            total += n + 1 if m % (n+1) else 0
                    
        return total

[LeetCode] 170. Two Sum III - Data structure design

 Problem : https://leetcode.com/problems/two-sum-iii-data-structure-design/

M = Value - N.   Use hash table to find whether M exists when given Value and N.

class TwoSum:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.seen = {}
        self.memo = set()
        
    def add(self, number: int) -> None:
        """
        Add the number to an internal data structure..
        """
        
        if number in self.seen:
            self.seen[number] += 1
        else:
            self.seen[number] = 1
        
    def find(self, value: int) -> bool:
        """
        Find if there exists any pair of numbers which sum is equal to the value.
        """
        
        if value in self.memo: return True

        for n in self.seen.keys():
            if value - n == n:
                if self.seen.get(n, 0) >= 2: 
                    self.memo.add(value)
                    return True
            elif self.seen.get(value - n, 0) > 0: 
                self.memo.add(value)
                return True
        
        return False

[LeetCode] 389. Find the Difference

 Problem : https://leetcode.com/problems/find-the-difference/

Use hash table to find the difference:

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        counterS = Counter(s)
        counterT = Counter(t)
        
        for k, v in counterT.items():
            if counterS[k] != v:
                return k

[LeetCode] 387. First Unique Character in a String

 Problem : https://leetcode.com/problems/first-unique-character-in-a-string/

class Solution:
    def firstUniqChar(self, s: str) -> int:
        counter = Counter(s)
        
        for i, n in enumerate(s):
            if counter[n] == 1: return i
        
        return -1

[LeetCode] 383. Ransom Note

Problem : https://leetcode.com/problems/ransom-note/

Time Complexity = O ( M + N  ).  M = len ( magazine ), N = len ( ransomNote )

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        counter = Counter(magazine)
        
        for r in ransomNote:
            if r not in counter or counter[r] <= 0:
                return False
            else:
                counter[r] -= 1
        
        return True

[LeetCode] 381. Insert Delete GetRandom O(1) - Duplicates allowed

 Problem: https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/

Similar to the problem # 380, to get O(1) time complexity for deleting operation, we need to save the index of each value in the value list.  Because it allows duplicated value be inserted and deleting item from bidirectional linked list is O(1). we can manage nodes with same value in a bidirectional linked list. Then the hash table saves the index of the last item of one value's bidirectional linked list. 

class Node:
    def __init__(self, val, pre, nxt):
        self.val = val
        self.pre = pre
        self.nxt = nxt
        
        
class RandomizedCollection:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        
        # nodes with same value are linked as a bidirectional linked list
        # dict[K] save the index of the last node of number K's linked list 
        self.dict = defaultdict(lambda: -1)
        
        # save all values
        self.list = []
        

    def insert(self, val: int) -> bool:
        """
        Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
        """
        
        index = len(self.list)
        
        if self.dict[val] == -1:
            node = Node(val = val, pre = -1, nxt = -1)
            
            self.dict[val] = index
            self.list.append(node)
            
            return True
        else:
            pre = self.dict[val]
            node = Node(val = val, pre = pre, nxt = -1)
            
            # append to the existing bidirectional link
            
            preNode = self.list[pre]
            preNode.nxt = index
            
            self.dict[val] = index
            self.list.append(node)
            
            return False

    def remove(self, val: int) -> bool:
        """
        Removes a value from the collection. Returns true if the collection contained the specified element.
        """
        
        if self.dict[val] == -1:
            return False
        
        # use the last item of self.list to replace the removed item
        # and update the the altered item indices
        
        index = self.dict[val]
        node = self.list[index]
        
        if node.pre == -1:
            self.dict[val] = -1
        else:
            # remove from the removed node's bidirectional linked list
            self.dict[val] = node.pre
            self.list[node.pre].nxt = -1
            
        tailIndex = len(self.list) - 1
        tailNode = self.list.pop()

        if index != tailIndex:
            self.list[index] = tailNode

            # update tailNode's bidirectional linked list
            if self.dict[tailNode.val] == tailIndex:
                self.dict[tailNode.val] = index

            if tailNode.pre != -1:
                self.list[tailNode.pre].nxt = index

            if tailNode.nxt != -1:
                self.list[tailNode.nxt].pre = index
                
        return True
    
    def getRandom(self) -> int:
        """
        Get a random element from the collection.
        """
        
        index = random.randint(0, len(self.list) - 1)
        return self.list[index].val


# Your RandomizedCollection object will be instantiated and called as such:
# obj = RandomizedCollection()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

P.S. We can also use hash set to save all list item indices of a given value. Deleting item from hash set is also O(1).

[LeetCode] 380. Insert Delete GetRandom O (1)

Problem : https://leetcode.com/problems/insert-delete-getrandom-o1/ 

The crux is using the last element of the list to replace the element needs to be removed to meet the requirement of O(1) deleting operation.

import random

class RandomizedSet:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        
        self.dict = {}
        self.list = []
        

    def insert(self, val: int) -> bool:
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        """
        
        res = val not in self.dict
        
        if res:
            self.dict[val] = len(self.list)
            self.list.append(val)
        return res

    def remove(self, val: int) -> bool:
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        """
        res = val in self.dict
        if res:
            # use the last element to replace the removed element
            index = self.dict[val]
            del self.dict[val]
            
            if index != len(self.list) - 1:
                self.list[index] = self.list[-1]
        
                # update element index and popup the last element from list
                self.dict[self.list[index]] = index
                
            self.list.pop()
        return res
        

    def getRandom(self) -> int:
        """
        Get a random element from the set.
        """
        
        pick = random.randint(0, len(self.list) - 1)
        
        return self.list[pick]
        


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

[LeetCode] 335. Design Twitter

 Problem : https://leetcode.com/problems/design-twitter/

- Tweet be posted later may have smaller tweetId. So we need to save the time when the tweet be post.

- Should not allow user to follow themselves.

- Should not allow user to unfollow not-followed user.

from operator import itemgetter

class Twitter:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.timer = 1
        self.follows = defaultdict(set)
        self.tweets = defaultdict(list)

    def postTweet(self, userId: int, tweetId: int) -> None:
        """
        Compose a new tweet.
        """
        self.tweets[userId].append((self.timer, tweetId))
        self.timer += 1
        

    def getNewsFeed(self, userId: int) -> List[int]:
        """
        Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
        """
        
        allTweets = self.tweets[userId][:]
        
        for f in self.follows[userId]:
            allTweets.extend(self.tweets[f])
            
        
        allTweets.sort(reverse = True, key = itemgetter(0))
        allTweets = allTweets if len(allTweets) <= 10 else allTweets[:10]
        
        return [tweetId for _, tweetId in allTweets]
                

    def follow(self, followerId: int, followeeId: int) -> None:
        """
        Follower follows a followee. If the operation is invalid, it should be a no-op.
        """
        
        if followerId != followeeId:
            self.follows[followerId].add(followeeId)
        

    def unfollow(self, followerId: int, followeeId: int) -> None:
        """
        Follower unfollows a followee. If the operation is invalid, it should be a no-op.
        """
        
        if followerId != followeeId and followeeId in self.follows[followerId]:
            self.follows[followerId].remove(followeeId)
        


# Your Twitter object will be instantiated and called as such:
# obj = Twitter()
# obj.postTweet(userId,tweetId)
# param_2 = obj.getNewsFeed(userId)
# obj.follow(followerId,followeeId)
# obj.unfollow(followerId,followeeId)

[LeetCode] 350. Intersection of Two Arrays II

Problem : https://leetcode.com/problems/intersection-of-two-arrays-ii/

2 pointers solution:  

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
        
        result = []
        i = j = 0
        
        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:
                i += 1
            elif nums1[i] > nums2[j]:
                j += 1
            else:
                result.append(nums1[i])
                i += 1
                j += 1
        
        return result

When elements are stored on disk, use external sort algorithm to sort items first. Then use this 2 pointers approach to find the intersection.

Hash table based solutin:

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        counter1 = Counter(nums1)
        counter2 = Counter(nums2)
        
        result = []
        
        for k, v1 in counter1.items():
            v2 = counter2.get(k, 0)
            
            if min(v1, v2):
                result += [k] * min(v1, v2)
        
        return result

Edited on 09/17/2021. Update a simpler hash table based solution.

[LeetCode] 349. Intersection of Two Arrays

 Problem : https://leetcode.com/problems/intersection-of-two-arrays/

Binary search solution: 

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        
        def bsearch(nums, target):
            left, right = 0, len(nums)
            
            while left < right:
                mid = left + (right - left) // 2
                if nums[mid] == target:
                    return True
                if nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid
            
            return False
        
        result = []
        
        if len(nums1) > len(nums2) : nums1, nums2 = nums2, nums1
        
        nums1.sort()
        nums2.sort()
        
        for i, n in enumerate(nums1):
            if i - 1 >= 0 and nums1[i] == nums1[i-1]:
                continue
            
            if bsearch(nums2, n):
                result.append(n)
            
        
        return result

2 pointers solution:

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
        
        result = []
        
        i = j = 0
        
        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:
                i += 1
            elif nums1[i] > nums2[j]:
                j += 1
            else:
                if not result or result[-1] != nums1[i]:
                    result.append(nums1[i])
                i += 1
                j += 1
        
        return result

Hash table based solution:

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        seen = defaultdict(lambda : [0, 0])
        
        for n in nums1:
            seen[n][0] += 1
        
        for n in nums2:
            seen[n][1] += 1
            
        
        return filter(lambda n : seen[n][0] >= 1 and seen[n][1] >= 1, seen.keys())

[LeetCode] 336. Palindrome Pairs

 Problem : https://leetcode.com/problems/palindrome-pairs/

There are 3 cases can form a palindrome string.

1)  ABC + CBA

2)  CBA + [A-Palindrome-String] ABC 

3)  ABC[A-Palindrome-String]  + CBA   

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        
        def isPalindrome(w, left, right):
            while left < right:
                if w[left] != w[right]: return False
                left += 1
                right -= 1
            
            return True
        
        
        result = []
        seen = { k : v for v, k in enumerate(words) }
        lens = sorted({len(w) for w in words})
        
        for i, w in enumerate(words):
            # rw = reversed 'w'
            rw = w[::-1]
            
            # case abc -- cba
            if rw in seen and seen[rw] != i:
                result.append([i, seen[rw]])
                
            l = 0
            while lens[l] < len(rw):
                # case cba  -- ddabc                
                if isPalindrome(rw, 0, len(rw) - lens[l] - 1) and \
                   rw[len(w) - lens[l]:] in seen:
                    
                    result.append([i, seen[rw[len(w) - lens[l]:]]])
                # case abcdd -- cba
                if isPalindrome(rw, lens[l], len(rw)-1) and \
                   rw[:lens[l]] in seen:
                    result.append([seen[rw[:lens[l]]], i])
                
                l += 1
        
        return result

Use Trie to find possible suffix.

class TrieNode:
    def __init__(self, val):
        self.val = val
        self.index = -1
        self.nodes = {}


class Trie:
    def __init__(self):
        self.root = TrieNode('')
    
    def add(self, index, word):
        if not word:
            self.root.index = index
        else:
            p = self.root
            
            for w in word:
                if w in p.nodes:
                    p = p.nodes[w]
                else:
                    node = TrieNode(w)
                    p.nodes[w] = node
                    p = node
                    
            p.index = index
        
def isPalindrome(word):
    if not word: return True
    
    left, right = 0, len(word)-1
    
    while left < right and word[left] == word[right]:
        left += 1
        right -=1 
    
    return left >= right

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        trie = Trie()
        
        for index, word in enumerate(words):
            trie.add(index, word[::-1])
        
        result = []
        
        for index, word in enumerate(words):
            i = 0
            p = trie.root
                        
            # dfs
            stack = [(p, "")]
            
            while stack:
                p, suffix = stack.pop()
                
                if p.index != -1 and p.index != index and isPalindrome(word[i:] + suffix):
                    result.append((index, p.index))
                
                if not suffix and i < len(word) and word[i] in p.nodes:
                    stack.append((p.nodes[word[i]], ""))
                    i += 1
                else:
                    for n in p.nodes.values():
                        stack.append((n, n.val + suffix))
        return result

Edited on 06/13/2021. Add the Trie based solution.

[LeetCode] 316. Remove Duplicate Letters

 Problem : https://leetcode.com/problems/remove-duplicate-letters/

To form the smallest string in lexicographical order, we need to put the remaining smallest letters in front.

Time Complexity = O ( N )

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        seen = {}
        used = defaultdict(bool)
        
        # remember the last position the letter be seen
        for i, w in enumerate(s):
            seen[w] = i
        
        result = []
        
        for i, w in enumerate(s):
            if used[w]:
                continue
            
            # replace the selected letter
            # if the letter is larger than current one
            # and we still have this letter in the back
            while result and ord(result[-1]) > ord(w) and seen[result[-1]] > i:
                used[result[-1]] = False
                result.pop()
                
            result.append(w)
            used[w] = True
        
        return ''.join(result)

[LeetCode] 299. Bulls and Cows

 Problem : https://leetcode.com/problems/bulls-and-cows/

An intuitive solution based on hash table.

class Solution:
    def getHint(self, secret: str, guess: str) -> str:
        counterS = Counter(secret)
        
        bulls = 0
        for i, g in enumerate(guess):
            if g == secret[i]:
                bulls += 1
                counterS[g] -= 1
        
        cows = 0
        for i, g in enumerate(guess):
             if g != secret[i] and g in counterS and counterS[g] > 0:
                cows += 1
                counterS[g] -= 1
        
        return "{}A{}B".format(bulls, cows)

[LeetCode] 290. Word Pattern

 Problem : https://leetcode.com/problems/word-pattern/

Use 2 hash maps to save the mapping relationship.

class Solution:
    def wordPattern(self, pattern: str, str: str) -> bool:
        word = str.split(' ')
        
        w2p = defaultdict(lambda : '')
        p2w = defaultdict(lambda : '')
        
        if len(word) != len(pattern):
            return False
        
        for i in range(len(pattern)):
            if pattern[i] not in p2w and word[i] not in w2p:
                p2w[pattern[i]] = word[i]
                w2p[word[i]] = pattern[i]
            
            elif p2w[pattern[i]] != word[i] or w2p[word[i]] != pattern[i]:
                return False
        
        
        return True

[LeetCode] 268. Missing Number

Problem : https://leetcode.com/problems/missing-number/

Hash table based solution:

Time complexity = O ( N )

Space complexity = O ( N )

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        memo = set(nums)
        
        for n in nums:
            if n < len(nums) and n + 1 not in memo:
                return n + 1
        
        return 0

Bit manipulation based solution:

Time complexity = O ( N )

Space complexity = O ( 1 )

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        missing = len(nums)
    
        for i, n in enumerate(nums):
            missing ^= i ^ n
            
        return missing

As it mentioned, the numbers are from 0 to n.

Now we use all of the valid indices [0, n] to XOR with all numbers. The result is the missing number.

[LeetCode] 260. Single Number III

 Problem : https://leetcode.com/problems/single-number-iii/

Hash table based solution:

Time complexity = O ( N )

Space complexity = O ( N )

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        return [x[0] for x in filter(lambda x: x[1] == 1, Counter(nums).items())]

Sort first then count numbers solution:

Time complexity = O ( N * LogN )

Space complexity = O ( 1 )

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        nums.sort()
        
        a = cntA = 0
        b = cntB = 0
        
        for n in nums:
            if cntA == 0:
                a = n
                cntA += 1
            elif a == n:
                cntA -= 1
            elif cntB == 0:
                b = n
                cntB += 1
            elif b == n:
                cntB -= 1
        
        
        return [a, b]

Bit manipulation based solution:

Time complexity = O ( N )

Space complexity = O ( 1 )

class Solution {
    public int[] singleNumber(int[] nums) {
        // Since all numbers except A and B appear twice
        // XOR = A ^ B
        int XOR = 0;
        for (int n : nums) {
            XOR ^= n;
        }
        
        // Find the first bit of the XOR from the right where bit == 1.
        // Because XR = A ^ B, this bit is either contribute by A or B.
        int offset = 0;
        while (offset < 32 && (XOR & (1 << offset)) == 0 ) {
            offset += 1;
        }
                
        // Use the bit of 'offset' as a flag to separate the original numbers to 2 groups
        // Group 1 : A, other numbers except B
        // Group 2 : B, other numbers except A
        // A = accumulated xor of numbers in group 1 
        // B = accumulated xor of number in group 2
        int A = 0, B = 0;
        for (int n : nums) {
            if ((n & (1 << offset)) != 0) {
                A ^= n;
            } else {
                B ^= n;
            }
        }
        
        return new int[] {A, B};
    }
}

Assume A and B are the 2 single numbers. Because all other numbers appear exactly twice. 

xor all numbers  =  A ^ B.

Then find the first bit of A ^ B = 1.   This bit is either from A or from B.

Use this bit to split the nums into 2 groups. Group 1 includes A and all other numbers except B. Group 2 includes B and all other numbers except A.

Since in each group there is only one single number,  result of xor all numbers in the group equals to the single number.

Edited on 11/07/2021. Update bit manipulation solution.

Edited on 05/31/2024. Update bit manipulation solution.

[LeetCode] 242. Valid Anagram

 Problem : https://leetcode.com/problems/valid-anagram/

Use hash table to count the characters in the string.

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return Counter(s) == Counter(t)

[LeetCode] 219. Contains Duplicate II

Problem : https://leetcode.com/problems/contains-duplicate-ii/

Remember the last position of each number. If find any number distinct indices difference <= k, that the answer.

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        seen = {}
        for i, n in enumerate(nums):
            if n in seen and i - seen[n] <= k:
                return True
            
            # update last position of 'n'
            # assume next 'n' position is j,
            # j -  the 'previous' seen[n] must larger than k
            # e.g.   previous seen[n] .... seen[n] .... j
            seen[n] = i
               
        return False