Longest Substring Without Repeating Characters – Python 3 (Week 12 -09)

Solution 1 HashMap

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        charmap = {}
        ans = 0
        i, j = 0, 0
        
        while i < len(s) and j < len(s):            
            if  s[j] not in charmap or charmap[s[j]] < i:
                charmap[s[j]] = j
                ans = max(ans, j - i + 1)
                j += 1
            else:                
                i = charmap[s[j]] + 1
                charmap[s[j]] = j
                ans = max(ans, j - i + 1)
                j += 1
                
        return ans

Time complexity : O ( n ) . Index j will iterate n times. Space complexity O(min(m,n)). We need O(k) space for the sliding window, where k is the size of the Set. The size of the Set is upper bounded by the size of the string n and the size of the charset/alphabet m.

Solution 2 ASCII and Array

   class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        
        ans = 0
        i = 0
        
        charmap = [0] * 256

        for j in range(len(s)):
            i = max(charmap[ord(s[j])], i)
            ans = max(ans, j - i + 1)
            charmap[ord(s[j])] = j + 1
            
        return ans

Time O(n). Space O(1).

Valid Sudoku – Python 3 (Week 12 – 08)

   class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row = [set([]) for i in range(9)]
        col = [set([]) for i in range(9)]
        grid = [set([]) for i in range(9)]
        
        for i in range(9):
            for j in range(9):
                
                if board[i][j] == '.':
                    continue
                if board[i][j] in row[i]:
                    return False
                if board[i][j] in col[j]:
                    return False
                
                gridIndex = i // 3 * 3 + j // 3
                print(gridIndex)
                
                if board[i][j] in grid[gridIndex]:
                    return False
                
                row[i].add(board[i][j])
                col[j].add(board[i][j])
                grid[gridIndex].add(board[i][j])
                
        return True

Time O(n^2). Space O(n^2).

#Group Anagrams – Python 3 (Week 12 – 06)

Solution 1

class Solution:
“””
@param strs: the given array of strings
@return: The anagrams which have been divided into groups
“””
def groupAnagrams(self, strs):
# write your code here
dic = {}
for item in sorted(strs):
sortedItem = ”.join(sorted(item))
dic[sortedItem] = dic.get(sortedItem, []) + [item]
return dic.values()

Time Complexity: O ( N K log ⁡ K ), where N N is the length of strs, and K K is the maximum length of a string in strs. Space Complexity: O ( N K ), the total information content stored in ans.

Solution 2

class Solution(object):
def groupAnagrams(self, strs):
ans = collections.defaultdict(list)
for s in strs:
ans[tuple(sorted(s))].append(s)
return ans.values()

Solution 3

class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
ans = collections.defaultdict(list)
for s in strs:
count = [0] * 26
for c in s:
count[ord(c) – ord(‘a’)] += 1
ans[tuple(count)].append(s)
return ans.values()

Time O ( N K ). Space O(N K).

Load Balancer – Python 3 (Week 12 – 05)

class LoadBalancer:
    def __init__(self):
        # do intialization if necessary
        self.server_ids = []
        self.id2index = {}
        

    """
    @param: server_id: add a new server to the cluster
    @return: nothing
    """
    def add(self, server_id):
        # write your code here
        if server_id in self.id2index:
            return
        self.server_ids.append(server_id)
        self.id2index[server_id] = len(self.server_ids) - 1

    """
    @param: server_id: server_id remove a bad server from the cluster
    @return: nothing
    """
    def remove(self, server_id):
        # write your code here
        if server_id not in self.id2index:
            return
        index = self.id2index[server_id]
        self.server_ids[index] = self.server_ids[-1]
        self.id2index[self.server_ids[-1]] = index
        self.server_ids.pop()
        del self.id2index[server_id]
        

    """
    @return: pick a server in the cluster randomly with equal probability
    """
    def pick(self):
        # write your code here
        import random
        index = random.randint(0, len(self.server_ids) - 1)
        return self.server_ids[index]

Time O(1). Space O(1).

Longest Consecutive Sequence – Python 3 (Week 12 – 04)

  class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if len(nums) < 1:
            return 0
        
        numsSet = set()
        for num in nums:
            numsSet.add(num)
        
        ans = 1
        for num in nums:
            if num in numsSet:
                numsSet.remove(num)                
                l = num - 1
                r = num + 1            
                while l in numsSet:
                    numsSet.remove(l)
                    l -= 1
                while r in numsSet:
                    numsSet.remove(r)
                    r += 1
                ans = max(ans, r - l - 1)
            
        return ans

Time O(n). Space O(n). n is len(nums).

Unique Word Abbreviation – Python 3 (Week 12 – 03)

class ValidWordAbbr:
    """
    @param: dictionary: a list of words
    """
    def __init__(self, dictionary):
        # do intialization if necessary
        self.dictCnt = collections.Counter(dictionary)
        self.abbCnt = collections.Counter([self.getAbbr(word) for word in dictionary])


    """
    @param: word: a string
    @return: true if its abbreviation is unique or false
    """
    def isUnique(self, word):
        # write your code here
        return self.dictCnt.get(word, 0) == self.abbCnt.get(self.getAbbr(word), 0)


    def getAbbr(self, word):
        if len(word) < 3:
            return word
        return word[0] + str(len(word) - 2) + word[-1]

Time O(1). Space O(1).

Word Abbreviation – Python 3 (Week 12 – 02)

class Solution:
    """
    @param dict: an array of n distinct non-empty strings
    @return: an array of minimal possible abbreviations for every word
    """
    def wordsAbbreviation(self, dict):
        # write your code here
        if not dict:
            return []
        ans = [''] * len(dict)
        count = {}
        r = 1 ## round
        for i in range(len(dict)):
            ans[i] = (self.getAbbr(dict[i], r))
            count[ans[i]] = count.get(ans[i],0) + 1
            
        while True:
            r += 1
            unique = True 
            for i in range(len(dict)):
                if count[ans[i]] > 1:
                    ans[i] = self.getAbbr(dict[i], r)
                    count[ans[i]] = count.get(ans[i],0) + 1
                    unique = False
            if unique:
                break

        return ans
        
        
        
        
        
    def getAbbr(self, s, p): ## p is prefix, round
        if len(s) < 3 + p:
            return s
        return s[:p] + str(len(s) - 1 - p) + s[- 1]

Find All Anagrams in a String – Python 3 (Week 12 – 01)

  class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        ans = []
        if len(s) < len(p) :
            return ans
        
        det = [0 for x in range(26)]
        
        for i in range(len(p)):
            det[ord(p[i]) - ord('a')] -= 1
            det[ord(s[i]) - ord('a')] += 1           
        abssum = 0
        for nums in det:
            abssum += abs(nums)            
        if abssum == 0:
            ans.append(0)

        
        for i in range(len(s) - len(p)):
            
            abssum -= abs(det[ord(s[i]) - ord('a')])
            abssum -= abs(det[ord(s[i + len(p) ]) - ord('a')])

            det[ord(s[i]) - ord('a')] -= 1
            det[ord(s[i + len(p)]) - ord('a')] += 1

            abssum += abs(det[ord(s[i]) - ord('a')]) 
            abssum += abs(det[ord(s[i + len(p)]) - ord('a')])

            if abssum == 0:
                ans.append(i + 1)
                
        return ans

Time O(n). Space O(1).

Longest Consecutive Sequence – Java

   public class Solution {
    /**
     * @param num: A list of integers
     * @return: An integer
     */
    public int longestConsecutive(int[] num) {
        // write your code here
        
        if (num == null) {
            return 0;
        }
        
        Set<Integer> set = new HashSet<>();
        for (int item : num) {
            set.add(item);
        }
        
        int ans = 0;
        
        for (int item : num) {
            if (set.contains(item)) {
                set.remove(item); 
                
                int l = item - 1;
                int r = item + 1;
                while (set.contains(l)) {
                    set.remove(l);
                    l--;
                }
                
                while (set.contains(r)) {
                    set.remove(r);
                    r++;
                }
                ans = Math.max(ans, r - l - 1);
            }
        }    
        return ans;
    }
}

Time O(n). Space O(1).

Design a site like this with WordPress.com
Get started