# Find the Shortest Superstring

Given an array A of strings, find any smallest string that contains each string in `A` as a substring.

We may assume that no string in `A` is substring of another string in `A`.

```Example 1:
Input: ["alex","loves","leetcode"]
Output: "alexlovesleetcode"
Explanation: All permutations of "alex","loves","leetcode" would also be accepted.
```
```Example 2:
Input: ["catg","ctaagt","gcta","ttca","atgcatc"]
Output: "gctaagttcatgcatc"```

Note:
`1 <= A.length <= 12`
`1 <= A[i].length <= 20`

Solution 1 (Naive and TLE):
At the very first, I did this solution that naively using DFS to search each possible solution, and finally we can pick up the shortest one. It works on small test set but got TLE on large sets.

```from functools import lru_cache

class Solution:
@lru_cache(None)
def combinateStrings(self, str1, str2):
for i in range(len(str2), -1, -1):
if str1.endswith(str2[:i]):
return str1 + str2[i:]

def shortestSuperstring(self, A):

def func(current_list, result, results):
if not current_list:
results.append(result)

for s in current_list:
current_list.remove(s)
func(current_list, self.combinateStrings(result, s), results)
func(current_list, self.combinateStrings(s, result), results)
current_list.append(s)

results = []

func(A, "", results)

return min(results, key= lambda x: len(x))```

# Best Time to Buy and Sell Stock with Transaction Fee

Your are given an array of integers `prices`, for which the `i`-th element is the price of a given stock on day `i`; and a non-negative integer `fee` representing a transaction fee.

You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)

Return the maximum profit you can make.

```Example 1:

Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
Buying at prices = 1Selling at prices = 8Buying at prices = 4Selling at prices = 9The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.```

Note:
`0 < prices.length <= 50000`.
`0 < prices[i] < 50000`.
`0 <= fee < 50000`.

```class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
sell = 0

for price in prices:
# Not buy or pay current price and fee

# Not sell or get current price
sell = max(sell, buy + price)

return sell```

# Reverse Pairs

Given an array `nums`, we call `(i, j)` an important reverse pair if `i < j` and `nums[i] > 2*nums[j]`.

You need to return the number of important reverse pairs in the given array.

Example1:

```Input: [1,3,2,3,1]
Output: 2```

Example2:

```Input: [2,4,3,5,1]
Output: 3```

Note:

1. The length of the given array will not exceed `50,000`.
2. All the numbers in the input array are in the range of 32-bit integer.
```# Solution 1: Using Binary Index Tree, which has O(nlogn) time complexity.

class BIT():
def __init__(self, n):
self.n = n + 1
self.sums =  * self.n

def update(self, i, delta):
while i < self.n:
self.sums[i] += delta
i += i & (-i)

def query(self, i):
res = 0
while i > 0:
res += self.sums[i]
i -= i & (-i)
return res

class Solution:
def reversePairs(self, nums: List[int]) -> int:
sorted_nums = sorted(list(set(nums + [x * 2 for x in nums])))
tree = BIT(len(sorted_nums))

res = 0
ranks = {}

for i, n in enumerate(sorted_nums):
ranks[n] = i + 1

for n in nums[::-1]:
res += tree.query(ranks[n] - 1)
tree.update(ranks[n * 2], 1)

return res```
```# Solution 2: At this time, we are going to use bisect. Got inspiration from Merge Sort (Divide and Conquer).

class Solution:
def reversePairs(self, nums: List[int]) -> int:
ranks = list()
ans = 0

for n in reverse(nums):
ans += bisect.bisect_left(ranks, n)
bisect.insort_left(ranks, n * 2)

return ans
```

# Largest Rectangle in Histogram

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = `[2,1,5,6,2,3]`.

The largest rectangle is shown in the shaded area, which has area = `10` unit.

Example:

```Input: [2,1,5,6,2,3]
Output: 10```

Actually, I have met this problem on the online assessment of Amazon a few days ago.

IT IS A REALLY TOUGH QUESTION FOR MY DUMB BRAIN!

```class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
heights.append(0)
stack = [-1]
ans = 0

for i in range(len(heights)):
while heights[i] < heights[stack[-1]]:
h = heights[stack.pop()]
w = i - stack[-1] - 1
ans = max(ans, h * w)
stack.append(i)

return ans```

# Is Graph Bipartite?

Given an undirected `graph`, return `true` if and only if it is bipartite.

Recall that a graph is bipartite if we can split it’s set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.

The graph is given in the following form: `graph[i]` is a list of indexes `j` for which the edge between nodes `i` and `j` exists.  Each node is an integer between `0` and `graph.length - 1`.  There are no self edges or parallel edges: `graph[i]` does not contain `i`, and it doesn’t contain any element twice.

```Example 1:
Input: [[1,3], [0,2], [1,3], [0,2]]
Output: true
Explanation:
The graph looks like this:
0----1
|    |
|    |
3----2
We can divide the vertices into two groups: {0, 2} and {1, 3}.
```
```Example 2:
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
Explanation:
The graph looks like this:
0----1
| \  |
|  \ |
3----2
We cannot find a way to divide the set of nodes into two independent subsets.
```

Note:

• `graph` will have length in range `[1, 100]`.
• `graph[i]` will contain integers in range `[0, graph.length - 1]`.
• `graph[i]` will not contain `i` or duplicate values.
• The graph is undirected: if any element `j` is in `graph[i]`, then `i` will be in `graph[j]`.
```class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
color = collections.defaultdict(lambda: -1)

def dfs(v, cur_color):
if color[v] != -1: return color[v] == cur_color
color[v] = cur_color
return all(dfs(e, cur_color ^ 1) for e in graph[v])

return all(dfs(v, 0) for v in range(len(graph)) if color[v] == -1)```

# Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

Example 1:

```Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because `"leetcode"` can be segmented as `"leet code"`.
```

Example 2:

```Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because `"`applepenapple`"` can be segmented as `"`apple pen apple`"`.
Note that you are allowed to reuse a dictionary word.
```

Example 3:

```Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false```
```# TLE solution
class Solution:
def helper(self, s):
if not s: return True
return any(self.helper(s[len(word):]) for word in self.wordDict if s.startswith(word))

def wordBreak(self, s: str, wordDict: List[str]) -> bool:
self.wordDict = wordDict
return self.helper(s)```
```# Basic DP
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
dp = [False] * len(s)

for i in range(len(s)):
for word in wordDict:
if s[:i+1].endswith(word) and (dp[i-len(word)] or i-len(word) == -1):
dp[i] = True

return dp[-1]```
```# Advanced DP
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
dp = [True]
for i in range(1, len(s)+1):
dp += any(dp[j] and s[j:i] in wordDict for j in range(i)),
return dp[-1]```

# Increasing Triplet Subsequence

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.

Example 1:

```Input: [1,2,3,4,5]
Output: true```

Example 2:

```Input: [5,4,3,2,1]
Output: false```

History is always recurrent.

At the very first, I thought it is a typical dp question, and then I wrote a classical dp solution, and then I got a TLE…

This AC solution I actually checked it out from discuss board, that is really smart.

```class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
N = len(nums)
first = float("inf")
second = float("inf")

for i in range(N):
if nums[i] < first:
first = nums[i]

elif first < nums[i] < second:
second = nums[i]

if nums[i] > second:
return True

return False```

# Evaluate Division

Equations are given in the format `A / B = k`, where `A` and `B` are variables represented as strings, and `k` is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return `-1.0`.

Example:
Given `a / b = 2.0, b / c = 3.0.`
queries are: `a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .`
return `[6.0, 0.5, -1.0, 1.0, -1.0 ].`

The input is: `vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries `, where `equations.size() == values.size()`, and the values are positive. This represents the equations. Return `vector<double>`.

According to the example above:

```equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. ```

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

```class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
graph = dict()

# Build graph
for (a, b), value in zip(equations, values):
graph[a] = graph.get(a, []) + [(b, value)]
graph[b] = graph.get(b, []) + [(a, 1/value)]

def check(source, target):
# If there is any one number of the query didn't appear in the graph, answer certainly doesn't exist.
if source not in graph or target not in graph:
return -1.0

visited = set()
stack = collections.deque([(source, 1.0)])

while stack:
front, current = stack.popleft()

if front == target:
return current

for back, value in graph[front]:
if back not in visited:
stack.append((back, current * value))

return -1.0

return [check(source, target) for (source, target) in queries]```

↓Code inside ↓