Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. *### Example 1 Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. *### Example 2 Input: "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. *### Example 3 Input: "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

by lek tin in "algorithm" access_time 1-min read

Before and After Puzzle

Given a list of phrases, generate a list of Before and After puzzles. A phrase is a string that consists of lowercase English letters and spaces only. No space appears in the start or the end of a phrase. There are no consecutive spaces in a phrase. Before and After puzzles are phrases that are formed by merging two phrases where the last word of the first phrase is the same as the first word of the second phrase.

by lek tin in "algorithm" access_time 2-min read

Verifying an Alien Dictionary

In an alien language, surprisingly they also use english lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters. Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographicaly in this alien language. Example 1 Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz" Output: true Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.

by lek tin in "algorithm" access_time 2-min read

Subarray Sum Equals K

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k. Example 1 «««< HEAD dev Input:nums = [1,1,1], k = 2 Output: 2 Note The length of the array is in range [1, 20,000]. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

by lek tin in "algorithm" access_time 2-min read

Find Anagram Mappings

Given two lists A and B, and B is an anagram of A. B is an anagram of A means B is made by randomizing the order of the elements in A. We want to find an index mapping P, from A to B. A mapping P[i] = j means the ith element in A appears in B at index j. These lists A and B may contain duplicates. If there are multiple answers, output any of them.

by lek tin in "algorithm" access_time 1-min read

Super Ugly Number

Write a program to find the nthsuper ugly number. Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. Example: Input: n = 12, primes = [2,7,13,19] Output: 32 Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12 super ugly numbers given primes = [2,7,13,19] of size 4. Note 1 is a super ugly number for any given primes. The given numbers in primes are in ascending order.

by lek tin in "algorithm" access_time 1-min read

Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Your algorithm should run in O(n) complexity. Example Input: [100, 4, 200, 1, 3, 2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4. Solution # Time: `O(n)` class Solution: def longestConsecutive(self, nums: List[int]) -> int: # Count occurence of nums mapping = {} for num in nums: mapping[num] = True # init longest length longest = 0 # iterate over nums for num in nums: if num in mapping: # num exists in mapping => init l = 1 l = 1 # num was counted, so we delete num del mapping[num] left, right = num-1, num+1 # Move left while left in mapping: # left was counted, so we delete left del mapping[left] left -= 1 l += 1 # Move right while right in mapping: # right was counted, so we delete right del mapping[right] right += 1 l += 1 # Update longest longest = max(longest, l) return longest

by lek tin in "algorithm" access_time 1-min read

Two Sum Iii Data Structure Design Design

Design and implement a TwoSum class. It should support the following operations: add and find. add - Add the number to an internal data structure. find - Find if there exists any pair of numbers which sum is equal to the value. Example 1 add(1); add(3); add(5); find(4) -> true find(7) -> false Example 2 add(3); add(1); add(2); find(3) -> true find(6) -> false Solution # Time: add is o(1), find is o(n) # Space: `O(n)` class TwoSum: def __init__(self): """ Initialize your data structure here.

by lek tin in "algorithm" access_time 1-min read

Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice. Example Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1]. Solution # time: `O(n)` # space: `O(n)` class Solution: def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ res = [-1, -1] if nums == None or len(nums) < 2: return res solutionMap = {} for pos in range(len(nums) - 1): if (target - nums[pos]) in solutionMap: res[0] = solutionMap[target - nums[pos]] res[1] = pos break solutionMap[nums[pos]] = pos return res # time: o(nlogn) # space: o(1) class Pair: def __init__(self, index, val): self.

by lek tin in "algorithm" access_time 2-min read

Copy List With Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list. Solution Solution 1: Insert cloned nodes in between original nodes then connect the cloned nodes # Definition for singly-linked list with a random pointer. # class RandomListNode(object): # def __init__(self, x): # self.label = x # self.next = None # self.

by lek tin in "algorithm" access_time 2-min read