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;
}
};