Longest Substring With at Most Two Distinct Characters

Given a string s, find the length of the longest substring t that contains at most 2 distinct characters. Example 1 Input: "eceba" Output: 3 Explanation: t is "ece" which its length is 3. Example 2 Input: "ccaabbb" Output: 5 Explanation: t is "aabbb" which its length is 5. Solution class Solution { public int lengthOfLongestSubstringTwoDistinct(String s) { HashMap<Character, Integer> countMap = new HashMap<Character, Integer>(); int left = 0; int max = 0; for (int i = 0; i < s.

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

Longest Substring With at Most K Distinct Characters

Given a string, find the length of the longest substring T that contains at most k distinct characters. Example 1 Input: s = "eceba", k = 2 Output: 3 Explanation: T is "ece" which its length is 3. Example 2 Input: s = "aa", k = 1 Output: 2 Explanation: T is "aa" which its length is 2. Solution class Solution { public int lengthOfLongestSubstringKDistinct(String s, int k) { Map<Character, Integer> countMap = new HashMap<>(); int left = 0; int max = 0; for(int i = 0; i < s.

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

Maximum Frequency Stack

Implement FreqStack, a class which simulates the operation of a stack-like data structure. FreqStack has two functions: push(int x), which pushes an integer x onto the stack. pop(), which removes and returns the most frequent element in the stack. If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned. Example 1 Input: ["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"], [[],[5],[7],[5],[7],[4],[5],[],[],[],[]] Output: [null,null,null,null,null,null,null,5,7,5,4] Explanation: After making six .

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

Most Common Word

Given a paragraph and a list of banned words, return the most frequent word that is not in the list of banned words. It is guaranteed there is at least one word that isn’t banned, and that the answer is unique. Words in the list of banned words are given in lowercase, and free of punctuation. Words in the paragraph are not case sensitive. The answer is in lowercase. Example: Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.

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

Find All Anagrams in a String

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s. Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100. The order of output does not matter. Example 1 Input: s: "cbaebabacd" p: "abc" Output: [0, 6] Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc".

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

Encode and Decode Tinyurl

Note This is a companion problem to the System Design problem: Design TinyURL. TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk. Design the encode and decode methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.

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

LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put. get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

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

Count Primes

Count the number of prime numbers less than a non-negative number, n. Example Input: 10 Output: 4 Explanation There are 4 prime numbers less than 10, they are 2, 3, 5, 7. Solution class Solution: def countPrimes(self, n): """ :type n: int :rtype: int """ if n <= 2: return 0 marked = [0] * (n-1) for i in range(int(n**0.5)+1): if marked[i] != 1: prime = i + 2 for j in range(prime**2-2, n-1, prime): marked[j] = 1 count = 0 for c, k in enumerate(marked): # We are counting numbers less than n, hence len(marked)-1 if k == 0 and c < len(marked)-1: count += 1 return count Cleaner version

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

Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements. For example, Given [1,1,1,2,2,3] and k = 2, return [1,2]. Note You may assume k is always valid, 1 ≤ k ≤ number of unique elements. Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size. Solution class Solution: def topKFrequent(self, nums, k): """ :type nums: List[int] :type k: int :rtype: List[int] """ freqMap = dict() for num in nums: if freqMap.

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

Valid Anagram

Given two strings s and t , write a function to determine if t is an anagram of s. Example 1: Input: s = "anagram", t = "nagaram" Output: true Example 2: Input: s = "rat", t = "car" Output: false Note You may assume the string contains only lowercase alphabets. Follow-up What if the inputs contain unicode characters? How would you adapt your solution to such case? Solution (using prime numbers) this approach is elegant but noted that if the strings are too long, the total sums maybe too big (overflow)

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