Remove Duplicate Letters

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results. Example 1 Input: "bcabc" Output: "abc" Example 2 Input: "cbacdcbc" Output: "acdb" Example 3 Input: "cba" Output: "cba" Solution class Solution: def removeDuplicateLetters(self, s: str) -> str: stack = [] seen = set() last_indices = {c: i for i, c in enumerate(s)} for i, c in enumerate(s): print(c, seen, stack) if c not in seen: while stack and c < stack[-1] and i < last_indices[stack[-1]]: seen.

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

Valid Sudoku

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules: Each row must contain the digits 1-9 without repetition. Each column must contain the digits 1-9 without repetition. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition. A partially filled sudoku which is valid. The Sudoku board could be partially filled, where empty cells are filled with the character '.

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

Interval List Intersections

Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order. Return the intersection of these two interval lists. (Formally, a closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b. The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval.

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

Scramble String

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively. Below is one possible representation of s1 = "great": great / \ gr eat / \ / \ g r e at / \ a t To scramble the string, we may choose any non-leaf node and swap its two children. For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

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

Palindrome Partitioning Ii

Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s. Example Input: "aab" Output: 1 Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut. Solution (DP) class Solution: def minCut(self, s: str) -> int: N = len(s) # valid[i][j] = True if s[i~j] IS palindrome, or False if IS NOT palindrome valid = [ [True for _ in range(N)] for _ in range(N) ] # min cuts of s[0~i] dp = [N for _ in range(N)] for l in range(2, N+1): for i in range(N-l+1): j = i+l-1 valid[i][j] = s[i]==s[j] and valid[i+1][j-1] for i in range(N): if valid[0][i]: # no cuts needed dp[i] = 0 continue for j in range(i): if valid[j+1][i]: #.

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

Palindrome Permutation

Given a string, determine if a permutation of the string could form a palindrome. Example 1 Input: "code" Output: false Example 2 Input: "aab" Output: true Example 3 Input: "carerac" Output: true Solution class Solution: def canPermutePalindrome(self, s: str) -> bool: lookup = set() for c in s: if c not in lookup: lookup.add(c) else: lookup.remove(c) return len(lookup) <= 1

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

First Unique Character in a String

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1. Example 1 s = "leetcode" return 0. Example 2 s = "loveleetcode", return 2. Solution Java class Solution { public int firstUniqChar(String s) { int[] counter = new int[256]; for ( char c: s.toCharArray() ) { counter[c] += 1; } for ( int i = 0; i < s.length(); i++) { if (counter[s.

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

Max Queue

Implement a MaxQueue class that has the following methods: public interface MaxQueue { public void add(Long l); public Long poll(); public Long pollMax(); } All 3 operations should take on average O(logN) time. Solution // "static void main" must be defined in a public class. public class Main { public static void main(String[] args) throws Exception { System.out.println("Hello World!"); DoubleLinkedList list = new DoubleLinkedList(); MaxQueue maxQ = new MaxQueue(); maxQ.add(5); maxQ.

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

String Compression

Given an array of characters, compress it in-place. The length after compression must always be smaller than or equal to the original array. Every element of the array should be a character (not int) of length 1. After you are done modifying the input array in-place, return the new length of the array. Follow up Could you solve it using only O(1) extra space? Example 1 Input: ["a","a","b","b","c","c","c"] Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"] Explanation: "aa" is replaced by "a2".

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

Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Each operand may be an integer or another expression. Note Division between two integers should truncate toward zero. The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation. Example 1 Input: ["2", "1", "+", "3", "*"] Output: 9 Explanation: ((2 + 1) * 3) = 9 Example 2 Input: ["4", "13", "5", "/", "+"] Output: 6 Explanation: (4 + (13 / 5)) = 6 Example 3 Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] Output: 22 Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22 Solution class Solution: def evalRPN(self, tokens: List[str]) -> int: if not tokens: return None stack = [] operators = set(["+", "-", "*", "/"]) N = len(tokens) curr = 0 while curr < N: while curr < N and tokens[curr] not in operators: stack.

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