Shortest Common Supersequence

Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If multiple answers exist, you may return any of them. (A string S is a subsequence of string T if deleting some number of characters from T (possibly 0, and the characters are chosen anywhere from T) results in the string S.) Example 1 Input: str1 = "abac", str2 = "cab" Output: "cabac" Explanation: str1 = "abac" is a subsequence of "cabac" because we can delete the first "c".

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

Longest Common Substring

Solution: public class LongestCommonString { /* Returns length of LCS for X[0..m-1], Y[0..n-1] */ int lcs( char[] X, char[] Y, int m, int n ) { // Size = m + 1, n + 1. int L[][] = new int[m+1][n+1]; Integer result = Integer.MIN_VALUE; /* Following steps build L[m+1][n+1] in bottom up fashion. Note ** that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */ for (int i=0; i<=m; i++) { for (int j=0; j<=n; j++) { if (i == 0 || j == 0) // Initialise L[0][0] = 0 L[i][j] = 0; else if (X[i-1] == Y[j-1]) // L[1][1] = L[0][0] + 1 = 0 + 1 = 1 L[i][j] = L[i-1][j-1] + 1; else L[i][j] = 0; if (dp[i][j] > result) { result = dp[i][j]; } } } return result; }

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

Lexicographical Numbers

Given an integer n, return 1 - n in lexicographical order. For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9]. Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000. Solution (iterative) class Solution: def lexicalOrder(self, n: int) -> List[int]: res = [0 for i in range(n)] curr = 1 for i in range(n): res[i] = curr # lower digits if curr * 10 <= n: curr *= 10 # higher digits else: # if curr is greater than n, we reverse it by /10 if curr >= n: curr //= 10 curr += 1 # if curr becomes X00000, we need to get rid of the trailing 0's while curr % 10 == 0: curr //= 10 return res # Input: n = 50 # Output: [1,10,11,12,13,14,15,16,17,18,19,2,20,21,22,23,24,25,26,27,28,29,3,30,31,32,33,34,35,36,37,38,39,4,40,41,42,43,44,45,46,47,48,49,5,50,6,7,8,9] Solution (recursion) Recursion

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

Balanced Binary Tree

Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as: a binary tree in which the left and right subtrees of every node differ in height by no more than 1. Example 1 Given the following tree [3,9,20,null,null,15,7]: 3 / \ 9 20 / \ 15 7 Return true. Example 2 Given the following tree [1,2,2,3,3,null,null,4,4]: 1 / \ 2 2 / \ 3 3 / \ 4 4 Return false.

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

Print Binary Tree

Print a binary tree in an m*n 2D string array following these rules: The row number m should be equal to the height of the given binary tree. The column number n should always be an odd number. The root node’s value (in string format) should be put in the exactly middle of the first row it can be put. The column and the row where the root node belongs will separate the rest space into two parts (left-bottom part and right-bottom part).

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

Greatest Sum Divisible by Three

Given an array nums of integers, we need to find the maximum possible sum of elements of the array such that it is divisible by three. Example 1 Input: nums = [3,6,5,1,8] Output: 18 Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3). Example 2 Input: nums = [4] Output: 0 Explanation: Since 4 is not divisible by 3, do not pick any number.

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

Powerful Integers

Given two positive integers x and y, an integer is powerful if it is equal to x^i + y^j for some integers i >= 0 and j >= 0. Return a list of all powerful integers that have value less than or equal to bound. You may return the answer in any order. In your answer, each value should occur at most once. Example 1 Input: x = 2, y = 3, bound = 10 Output: [2,3,4,5,7,9,10] Explanation: 2 = 2^0 + 3^0 3 = 2^1 + 3^0 4 = 2^0 + 3^1 5 = 2^1 + 3^1 7 = 2^2 + 3^1 9 = 2^3 + 3^0 10 = 2^0 + 3^2 Example 2 Input: x = 3, y = 5, bound = 15 Output: [2,4,6,8,10,14] Note 1 <= x <= 100 1 <= y <= 100 0 <= bound <= 10^6 Hint If x^i > bound, the sum x^i + y^j can’t be less than or equal to the bound.

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

K Th Smallest in Lexicographical Order

Given integers n and k, find the lexicographically k-th smallest integer in the range from 1 to n. Note: 1 ≤ k ≤ n ≤ 10^9. Example Input: n: 13 k: 2 Output: 10 Explanation: The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10. Solution class Solution: def findKthNumber(self, n: int, k: int) -> int: if n < k or k < 1: return 0 if n < 10: return k curr = 1 k -= 1 while k > 0: leap, prev, next = 0, curr, curr+1 while prev <= n: # update leap leap += min(n+1, next) - prev prev *= 10 next *= 10 if leap <= k: curr += 1 print(leap, "<= k; curr =", curr) k -= leap else: curr *= 10 print(leap, "> k; curr =", curr) k -= 1 return curr # Input: n=1300, k=50 # order: [1,10,100,1000,1001,1002,1003,1004,1005,1006,1007,1008,1009,101,1010,1011,1012,1013,1014,1015,1016,1017,1018,1019,102,1020,1021,1022,1023,1024,1025,1026,1027,1028,1029,103,1030,1031,1032,1033,1034,1035,1036,1037,1038,1039,104,1040,1041,1042] # Output: # 412 > k; curr = 10 # 111 > k; curr = 100 # 11 <= k; curr = 101 # 11 <= k; curr = 102 # 11 <= k; curr = 103 # 11 <= k; curr = 104 # 11 > k; curr = 1040 # 1 <= k; curr = 1041 # 1 <= k; curr = 1042

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

Maximum Swap

Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get. Example 1 Input: 2736 Output: 7236 Explanation: Swap the number 2 and the number 7. Example 2 Input: 9973 Output: 9973 Explanation: No swap. Note The given number is in the range [0, 10^8] Solution class Solution: def maximumSwap(self, num: int) -> int: numChars = list(str(num)) n = len(numChars) last = [0 for i in range(10)] for i in range(n): last[ord(numChars[i])-ord("0")] = i for i in range(n): # test the biggest number first j = 9 # We wanna find out the largest digit on the right while j > int(ord(numChars[i])-ord("0")): if last[j] > i: temp = numChars[i] numChars[i] = numChars[last[j]] numChars[last[j]] = temp return int("".

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

Largest Component Size by Common Factor

Given a non-empty array of unique positive integers A, consider the following graph: There are A.length nodes, labelled A[0] to A[A.length - 1]; There is an edge between A[i] and A[j] if and only if A[i] and A[j] share a common factor greater than 1. Return the size of the largest connected component in the graph. Example 1 Input: [4,6,15,35] Output: 4 Example 2 Input: [20,50,9,63] Output: 2 Example 3 Input: [2,3,6,7,4,12,21,39] Output: 8 Note 1 <= A.

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