BellmanFord

0
2
4
7
-2
Single source shorted path from vetex 0 exist? yes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//O(V*E)
bool bellman_ford(int n, vector<vector<int>> &edges) {
vector<int> distance(n, INT_MAX);

distance[0] = 0;
for (int i = 0; i < n; i++) {
for (auto &edge : edges) {
int u = edge[0];
int v = edge[1];
int w = edge[2];

distance[v] = min(distance[v], distance[u] + w);
}
}

for (auto &edge : edges) {
int u = edge[0];
int v = edge[1];
int w = edge[2];

if (distance[v] > distance[u] + w)
return false;
}

for (int d : distance)
cout << d << endl;

return true;
}

int main()
{
int n = 5;
vector<vector<int>> edges = {{0,1,6},{0,3,7},{1,2,5},{1,3,8},{1,4,-4},
{2,1,-2},{3,2,-3},{3,4,9},{4,0,2},{4,2,7}};
bool ret = bellman_ford(n, edges);
printf("Single source shorted path from vetex 0 exist? %s\n", ret ? "yes" : "no");

return 0;
}

leetcode 787 - Cheapest Flights Within K Stops

https://leetcode.com/problems/cheapest-flights-within-k-stops/

There are n cities connected by m flights. Each flight starts from city u and arrives at v with a price w.

Now given all the cities and flights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1.

Example 1:
Input:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
Output: 200
Explanation:
The graph looks like this:

The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.
Example 2:
Input:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
Output: 500
Explanation:
The graph looks like this:

The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked blue in the picture.

Constraints:

The number of nodes n will be in range [1, 100], with nodes labeled from 0 to n - 1.
The size of flights will be in range [0, n * (n - 1) / 2].
The format of each flight will be (src, dst, price).
The price of each flight will be in the range [1, 10000].
k is in the range of [0, n - 1].
There will not be any duplicated flights or self cycles.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
vector<vector<vector<int>>> graph(n);

for (auto &flight : flights)
graph[flight[0]].push_back({flight[1], flight[2]}); //u => {v, price}

vector<int> prices(n, INT_MAX);
queue<pair<int,int>> q; //{v, price}
q.push({src, 0});

while (!q.empty() && K >= -1) {
int size = q.size();

bool next = false;

for (int i = 0; i < size; i++) {
auto p = q.front(); q.pop();
int v = p.first;
int price = p.second;

if (price >= prices[v]) continue;

prices[v] = price;

for (auto &flight : graph[v]) {
q.push({flight[0], price + flight[1]});
next = true;
}
}

if (next)
K--;
}

return prices[dst] == INT_MAX ? -1 : prices[dst];
}
};

leetcode 743 - Network Delay Time

https://leetcode.com/problems/network-delay-time/
https://leetcode.com/problems/network-delay-time/discuss/283711/Python-Bellman-Ford-SPFA-Dijkstra-Floyd-clean-and-easy-to-understand

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
Example 2:

Input: times = [[1,2,1]], n = 2, k = 1
Output: 1
Example 3:

Input: times = [[1,2,1]], n = 2, k = 2
Output: -1

Constraints:

1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= ui, vi <= n
ui != vi
0 <= wi <= 100
All the pairs (ui, vi) are unique. (i.e., no multiple edges.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
//Dijikstra: O(ElogE), priority queue
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
vector<vector<vector<int>>> graph(n+1);

for (auto &time : times)
graph[time[0]].push_back({time[1], time[2]}); //{node, edge_len}

vector<int> path(n+1, INT_MAX);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; //{path_len, node}

pq.push({0, k});

while (!pq.empty()) {
auto p = pq.top(); pq.pop();

if (p.first >= path[p.second]) continue;

path[p.second] = p.first;

for (auto &edge : graph[p.second])
pq.push({p.first + edge[1], edge[0]});
}

int ans = INT_MIN;

for (int i = 1; i < (int)path.size(); i++) {
if (path[i] == INT_MAX) return -1;
ans = max(ans, path[i]);
}

return ans;
}
};

//Bellman-Ford; O(VE)
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
vector<int> distance(n+1, INT_MAX);

distance[k] = 0;

for (int i = 1; i <= n; i++) {
for (auto &time : times) {
int u = time[0];
int v = time[1];
int w = time[2];

if (distance[u] != INT_MAX)
distance[v] = min(distance[v], distance[u] + w);
}
}

int t = 0;

for (int i = 1; i <= n; i++) {
if (distance[i] == INT_MAX) return -1;
t = max(t, distance[i]);
}

return t;
}
};

//SPFA:
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
vector<vector<vector<int>>> graph(n+1);

for (auto &time : times)
graph[time[0]].push_back({time[1], time[2]}); //{node, edge_len}

vector<int> path(n+1, INT_MAX);
queue<pair<int,int>> q; //{path_len, node}

q.push({0, k});

while (!q.empty()) {
auto p = q.front(); q.pop();

if (p.first >= path[p.second]) continue;

path[p.second] = p.first;

for (auto &edge : graph[p.second])
q.push({p.first + edge[1], edge[0]});
}

int ans = INT_MIN;

for (int i = 1; i < (int)path.size(); i++) {
if (path[i] == INT_MAX) return -1;
ans = max(ans, path[i]);
}

return ans;
}
};

leetcode 1514 - Path with Maximum Probability

https://leetcode.com/problems/path-with-maximum-probability/

You are given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where edges[i] = [a, b] is an undirected edge connecting the nodes a and b with a probability of success of traversing that edge succProb[i].

Given two nodes start and end, find the path with the maximum probability of success to go from start to end and return its success probability.

If there is no path from start to end, return 0. Your answer will be accepted if it differs from the correct answer by at most 1e-5.

Example 1:

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
Output: 0.25000
Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.
Example 2:

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
Output: 0.30000
Example 3:

Input: n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
Output: 0.00000
Explanation: There is no path between 0 and 2.

Constraints:

2 <= n <= 10^4
0 <= start, end < n
start != end
0 <= a, b < n
a != b
0 <= succProb.length == edges.length <= 2*10^4
0 <= succProb[i] <= 1
There is at most one edge between every two nodes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
//Dijikstra, timeout
class Solution {
public:
double maxProbability(int n, vector<vector<int>>& edges,
vector<double>& succProb, int start, int end) {
vector<vector<pair<int, double>>> graph(n); //u => {v, prob}

for (int i = 0; i < (int)edges.size(); i++) {
auto &edge = edges[i];
graph[edge[0]].push_back({edge[1], succProb[i]});
graph[edge[1]].push_back({edge[0], succProb[i]});
}

vector<double> probs(n, 0);
priority_queue<pair<double, int>, vector<pair<double, int>>,
greater<pair<double, int>>> pq; //{prob, node}

pq.push({1.0, start});

while (!pq.empty()) {
auto &p = pq.top();
double prob = p.first;
int node = p.second;
pq.pop();

if (prob <= probs[node]) continue;
probs[node] = prob;

for (auto &edge : graph[node])
pq.push({prob * edge.second, edge.first});
}

return probs[end];
}
};

//BFS
class Solution {
public:
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
vector<vector<pair<int, double>>> graph(n); //u => {v, prob}

for (int i = 0; i < (int)edges.size(); i++) {
auto &edge = edges[i];
graph[edge[0]].push_back({edge[1], succProb[i]});
graph[edge[1]].push_back({edge[0], succProb[i]});
}

vector<double> probs(n, 0);
queue<pair<double, int>> q; //{prob, node}

q.push({1.0, start});

while (!q.empty()) {
auto &p = q.front();
double prob = p.first;
int node = p.second;
q.pop();

if (prob <= probs[node]) continue;
probs[node] = prob;

for (auto &edge : graph[node])
q.push({prob * edge.second, edge.first});
}

return probs[end];
}
};

leetcode 1764 - Form Array by Concatenating Subarrays of Another Array

https://leetcode.com/problems/form-array-by-concatenating-subarrays-of-another-array/

You are given a 2D integer array groups of length n. You are also given an integer array nums.

You are asked if you can choose n disjoint subarrays from the array nums such that the ith subarray is equal to groups[i] (0-indexed), and if i > 0, the (i-1)th subarray appears before the ith subarray in nums (i.e. the subarrays must be in the same order as groups).

Return true if you can do this task, and false otherwise.

Note that the subarrays are disjoint if and only if there is no index k such that nums[k] belongs to more than one subarray. A subarray is a contiguous sequence of elements within an array.

Example 1:

Input: groups = [[1,-1,-1],[3,-2,0]], nums = [1,-1,0,1,-1,-1,3,-2,0]
Output: true
Explanation: You can choose the 0th subarray as [1,-1,0,1,-1,-1,3,-2,0] and the 1st one as [1,-1,0,1,-1,-1,3,-2,0].
These subarrays are disjoint as they share no common nums[k] element.
Example 2:

Input: groups = [[10,-2],[1,2,3,4]], nums = [1,2,3,4,10,-2]
Output: false
Explanation: Note that choosing the subarrays [1,2,3,4,10,-2] and [1,2,3,4,10,-2] is incorrect because they are not in the same order as in groups.
[10,-2] must come before [1,2,3,4].
Example 3:

Input: groups = [[1,2,3],[3,4]], nums = [7,7,1,2,3,4,7,7]
Output: false
Explanation: Note that choosing the subarrays [7,7,1,2,3,4,7,7] and [7,7,1,2,3,4,7,7] is invalid because they are not disjoint.
They share a common elements nums[4] (0-indexed).

Constraints:

groups.length == n
1 <= n <= 10^3
1 <= groups[i].length, sum(groups[i].length) <= 10^3
1 <= nums.length <= 10^3
-10^7 <= groups[i][j], nums[k] <= 10^7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
bool canChoose(vector<vector<int>>& groups, vector<int>& nums) {
int i = 0;

for (auto &group : groups) {
i = find(nums, group, i);
if (i == -1)
return false;
i += group.size();
}

return true;
}

int find(vector<int>& nums, vector<int>& group, int i) {
int size = nums.size();

for (; i < size; i++) {
int k = 0;
for (int j = i; j < size; j++) {
if (nums[j] != group[k])
break;
if (++k == (int)group.size())
return i;
}
}

return -1;
}
};

leetcode 1640 - Check Array Formation Through Concatenation

https://leetcode.com/problems/check-array-formation-through-concatenation/

You are given an array of distinct integers arr and an array of integer arrays pieces, where the integers in pieces are distinct. Your goal is to form arr by concatenating the arrays in pieces in any order. However, you are not allowed to reorder the integers in each array pieces[i].

Return true if it is possible to form the array arr from pieces. Otherwise, return false.

Example 1:

Input: arr = [85], pieces = [[85]]
Output: true
Example 2:

Input: arr = [15,88], pieces = [[88],[15]]
Output: true
Explanation: Concatenate [15] then [88]
Example 3:

Input: arr = [49,18,16], pieces = [[16,18,49]]
Output: false
Explanation: Even though the numbers match, we cannot reorder pieces[0].
Example 4:

Input: arr = [91,4,64,78], pieces = [[78],[4,64],[91]]
Output: true
Explanation: Concatenate [91] then [4,64] then [78]
Example 5:

Input: arr = [1,3,5,7], pieces = [[2,4,6,8]]
Output: false

Constraints:

1 <= pieces.length <= arr.length <= 100
sum(pieces[i].length) == arr.length
1 <= pieces[i].length <= arr.length
1 <= arr[i], pieces[i][j] <= 100
The integers in arr are distinct.
The integers in pieces are distinct (i.e., If we flatten pieces in a 1D array, all the integers in this array are distinct).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
unordered_map<int, int> maps; //numer -> group

int size = pieces.size();
int n = 0;
for (int i = 0; i < size; i++) {
maps[pieces[i][0]] = i;
n += pieces[i].size();
}

size = arr.size();
if (size != n) return false;

int group = -1;
int group_i;

for (int i = 0; i < size; i++) {
if (group == -1 || group_i == pieces[group].size()) {
if (maps.count(arr[i]) == 0) return false;

group = maps[arr[i]];
group_i = 0;
}

if (arr[i] != pieces[group][group_i])
return false;

group_i++;
}

return group_i == pieces[group].size();
}
};

leetcode 1631 - Path With Minimum Effort

https://leetcode.com/problems/path-with-minimum-effort/
https://leetcode.com/problems/path-with-minimum-effort/discuss/909200/C%2B%2B-Concise-Dijikstra-algorithm-350ms

You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.

A route’s effort is the maximum absolute difference in heights between two consecutive cells of the route.

Return the minimum effort required to travel from the top-left cell to the bottom-right cell.

Example 1:

Input: heights = [[1,2,2],[3,8,2],[5,3,5]]
Output: 2
Explanation: The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells.
This is better than the route of [1,2,2,2,5], where the maximum absolute difference is 3.
Example 2:

Input: heights = [[1,2,3],[3,8,4],[5,3,5]]
Output: 1
Explanation: The route of [1,2,3,4,5] has a maximum absolute difference of 1 in consecutive cells, which is better than route [1,3,5,3,5].
Example 3:

Input: heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
Output: 0
Explanation: This route does not require any effort.

Constraints:

rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 10^6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
int minimumEffortPath(vector<vector<int>>& heights) {
int rows = heights.size(), cols = heights[0].size();

vector<vector<int>> effort(rows, vector<int>(cols, INT_MAX)); //{effort, x, y}

priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
pq.push({0, 0, 0});

int dir[5] = {0,-1,0,1,0};

while (!pq.empty()) {
auto v = pq.top(); pq.pop();
int r = v[1], c = v[2];

if (v[0] >= effort[r][c]) continue;

effort[r][c] = v[0];

for (int i = 0; i < 4; i++) {
int x = r + dir[i];
int y = c + dir[i+1];

if (x < 0 || x >= rows || y < 0 || y >= cols) continue;

int eff = max(v[0], abs(heights[r][c] - heights[x][y]));
pq.push({eff, x, y});
}
}

return effort[rows-1][cols-1];
}
};

Dijikstra

Single source shortest path
0 -> 0 = 0
0 -> 1 = 8
0 -> 2 = 9
0 -> 3 = 5
0 -> 4 = 7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
vector<int> shortest_path(int n, vector<vector<int>> &edges) {
vector<vector<vector<int>>> graph(n);

for (auto &edge : edges) {
int u = edge[0];
int v = edge[1];
int len = edge[2];
graph[u].push_back({v, len});
}

vector<int> length(n, INT_MAX);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; //{len, node}

pq.push({0,0});

while (!pq.empty()) {
auto p = pq.top(); pq.pop();

if (p.first >= length[p.second]) continue;

length[p.second] = p.first;

for (auto &edge : graph[p.second]) {
pq.push({p.first + edge[1], edge[0]});
}
}

return length;
}

int main()
{
//{u,v,len} u -> v = len
vector<vector<int>> edges = {{0,1,10},{0,3,5},{1,2,1},{1,3,2},{2,4,4},
{3,1,3},{3,4,2},{4,0,7},{4,2,6}};;
//total nodes: 0, 1, 2, ..., n-1
int n = 5;
vector<int> length = shortest_path(n, edges);
cout << "Single source shortest path" << endl;

for (int i = 0; i < n; i++)
cout << "0 -> " << i << " = " << length[i] << endl;

return 0;
}

leetcode 1765 - Map of Highest Peak

https://leetcode.com/problems/map-of-highest-peak/

You are given an integer matrix isWater of size m x n that represents a map of land and water cells.

If isWater[i][j] == 0, cell (i, j) is a land cell.
If isWater[i][j] == 1, cell (i, j) is a water cell.
You must assign each cell a height in a way that follows these rules:

The height of each cell must be non-negative.
If the cell is a water cell, its height must be 0.
Any two adjacent cells must have an absolute height difference of at most 1. A cell is adjacent to another cell if the former is directly north, east, south, or west of the latter (i.e., their sides are touching).
Find an assignment of heights such that the maximum height in the matrix is maximized.

Return an integer matrix height of size m x n where height[i][j] is cell (i, j)’s height. If there are multiple solutions, return any of them.

Example 1:

Input: isWater = [[0,1],[0,0]]
Output: [[1,0],[2,1]]
Explanation: The image shows the assigned heights of each cell.
The blue cell is the water cell, and the green cells are the land cells.
Example 2:

Input: isWater = [[0,0,1],[1,0,0],[0,0,0]]
Output: [[1,1,0],[0,1,1],[1,2,2]]
Explanation: A height of 2 is the maximum possible height of any assignment.
Any height assignment that has a maximum height of 2 while still meeting the rules will also be accepted.

Constraints:

m == isWater.length
n == isWater[i].length
1 <= m, n <= 1000
isWater[i][j] is 0 or 1.
There is at least one water cell.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
int rows = isWater.size(), cols = isWater[0].size();
vector<vector<int>> height(rows, vector<int>(cols, -1));
queue<pair<int,int>> q;

for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (isWater[r][c] == 1) {
height[r][c] = 0;
q.push({r, c});
}
}
}

vector<vector<int>> dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};

while (!q.empty()) {
auto p = q.front(); q.pop();

for (auto &dir : dirs) {
int r = p.first + dir[0];
int c = p.second + dir[1];

if (r < 0 || r >= rows || c < 0 || c >= cols || height[r][c] != -1)
continue;

q.push({r,c});
height[r][c] = height[p.first][p.second] + 1;
}
}

return height;
}
};

leetcode 1763 - Longest Nice Substring

https://leetcode.com/problems/longest-nice-substring/
https://leetcode.com/problems/longest-nice-substring/discuss/1075320/C%2B%2B-Divide-and-Conquer-O(N)-Time
https://leetcode.com/problems/longest-nice-substring/discuss/1074856/C%2B%2B-O(n)

A string s is nice if, for every letter of the alphabet that s contains, it appears both in uppercase and lowercase. For example, “abABB” is nice because ‘A’ and ‘a’ appear, and ‘B’ and ‘b’ appear. However, “abA” is not because ‘b’ appears, but ‘B’ does not.

Given a string s, return the longest substring of s that is nice. If there are multiple, return the substring of the earliest occurrence. If there are none, return an empty string.

Example 1:

Input: s = “YazaAay”
Output: “aAa”
Explanation: “aAa” is a nice string because ‘A/a’ is the only letter of the alphabet in s, and both ‘A’ and ‘a’ appear.
“aAa” is the longest nice substring.
Example 2:

Input: s = “Bb”
Output: “Bb”
Explanation: “Bb” is a nice string because both ‘B’ and ‘b’ appear. The whole string is a substring.
Example 3:

Input: s = “c”
Output: “”
Explanation: There are no nice substrings.
Example 4:

Input: s = “dDzeE”
Output: “dD”
Explanation: Both “dD” and “eE” are the longest nice substrings.
As there are multiple longest nice substrings, return “dD” since it occurs earlier.

Constraints:

1 <= s.length <= 100
s consists of uppercase and lowercase English letters.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
//O(N^2)
class Solution {
public:
string longestNiceSubstring(string s) {
int size = s.size();
int i = 0, j = 0;
int pos = 0, len = 0;

vector<int> count(256, 0);

for (int i = 0; i < size; i++) {
count[s[i]]++;

int j = check(s, count, i);
if (i - j + 1 > len) {
pos = j;
len = i - j + 1;
}
}

return s.substr(pos, len);
}

int check(string &s, vector<int> count, int end) {
for (int i = 0; i <= end; i++) {
if (good(count)) return i;

count[s[i]]--;
}

return end + 1;
}

bool good(vector<int> &count) {
for (char c = 'a'; c <= 'z'; c++) {
if (count[c] > 0 && count[c - ('a'-'A')] == 0)
return false;
}

for (char c = 'A'; c <= 'Z'; c++) {
if (count[c] > 0 && count[c + ('a'-'A')] == 0)
return false;
}

return true;
}
};

//O(N), Divide and Conquer
class Solution {
public:
#define LOWER 0
#define UPPER 1
string longestNiceSubstring(string s) {
int size = s.size();

if (size <= 1) return "";

vector<vector<bool>> count(26, vector<bool>(2, false));
for (char c : s) {
if (isupper(c))
count[c-'A'][UPPER] = true;
else
count[c-'a'][LOWER] = true;
}

string ans;
int i = 0;

while (i < size) {
if (!good(count, s[i])) {
i++;
continue;
}

int j = i;
while (j < size) {
if (!good(count, s[j])) break;

j++;
}

int len = j - i;
if (len == size) return s;

string tmp = longestNiceSubstring(s.substr(i, len));
if (tmp.size() > ans.size())
ans = tmp;

i = j + 1;
}

return ans;
}

bool good(vector<vector<bool>> &count, char c) {
if (islower(c) && count[c-'a'][UPPER] == false) return false;
if (isupper(c) && count[c-'A'][LOWER] == false) return false;

return true;
}
};