Welcome to Subscribe On Youtube
1763. Longest Nice Substring
Description
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.
Constraints:
1 <= s.length <= 100sconsists of uppercase and lowercase English letters.
Solutions
Solution 1: Set
We can directly enumerate the starting position of all substrings $i$, find all substrings starting with the character at this position, and use the hash table $s$ to record all the characters of the substring.
If there is a letter in the substring and the corresponding uppercase letter or lowercase letter cannot be found, then the condition is not met, otherwise the longest and earliest substring is taken.
Time complexity $O(n^2 \times C)$, space complexity $O(C)$. Where $n$ is the length of the string $s$, and $C$ is the size of the character set.
Solution 2
Similar to method one, we can directly enumerate the starting position of all substrings $i$, find all substrings starting with the character at this position, and use two integers $lower$ and $upper$ to record the occurrence of lowercase letters and uppercase letters in the substring respectively.
To determine whether the substring meets the conditions, you only need to determine whether the corresponding bits in $lower$ and $upper$ are both $1$.
Time complexity $O(n^2)$, space complexity $O(1)$. Where $n$ is the length of the string $s$.
-
class Solution { public String longestNiceSubstring(String s) { int n = s.length(); int k = -1; int mx = 0; for (int i = 0; i < n; ++i) { Set<Character> ss = new HashSet<>(); for (int j = i; j < n; ++j) { ss.add(s.charAt(j)); boolean ok = true; for (char a : ss) { char b = (char) (a ^ 32); if (!(ss.contains(a) && ss.contains(b))) { ok = false; break; } } if (ok && mx < j - i + 1) { mx = j - i + 1; k = i; } } } return k == -1 ? "" : s.substring(k, k + mx); } } // Solution 2 class Solution { public String longestNiceSubstring(String s) { int n = s.length(); int k = -1; int mx = 0; for (int i = 0; i < n; ++i) { int lower = 0, upper = 0; for (int j = i; j < n; ++j) { char c = s.charAt(j); if (Character.isLowerCase(c)) { lower |= 1 << (c - 'a'); } else { upper |= 1 << (c - 'A'); } if (lower == upper && mx < j - i + 1) { mx = j - i + 1; k = i; } } } return k == -1 ? "" : s.substring(k, k + mx); } } -
class Solution { public: string longestNiceSubstring(string s) { int n = s.size(); int k = -1, mx = 0; for (int i = 0; i < n; ++i) { unordered_set<char> ss; for (int j = i; j < n; ++j) { ss.insert(s[j]); bool ok = true; for (auto& a : ss) { char b = a ^ 32; if (!(ss.count(a) && ss.count(b))) { ok = false; break; } } if (ok && mx < j - i + 1) { mx = j - i + 1; k = i; } } } return k == -1 ? "" : s.substr(k, mx); } }; // Solution 2 class Solution { public: string longestNiceSubstring(string s) { int n = s.size(); int k = -1, mx = 0; for (int i = 0; i < n; ++i) { int lower = 0, upper = 0; for (int j = i; j < n; ++j) { char c = s[j]; if (islower(c)) lower |= 1 << (c - 'a'); else upper |= 1 << (c - 'A'); if (lower == upper && mx < j - i + 1) { mx = j - i + 1; k = i; } } } return k == -1 ? "" : s.substr(k, mx); } }; -
class Solution: def longestNiceSubstring(self, s: str) -> str: n = len(s) ans = '' for i in range(n): ss = set() for j in range(i, n): ss.add(s[j]) if ( all(c.lower() in ss and c.upper() in ss for c in ss) and len(ans) < j - i + 1 ): ans = s[i : j + 1] return ans # Solution 2 class Solution: def longestNiceSubstring(self, s: str) -> str: n = len(s) ans = '' for i in range(n): lower = upper = 0 for j in range(i, n): if s[j].islower(): lower |= 1 << (ord(s[j]) - ord('a')) else: upper |= 1 << (ord(s[j]) - ord('A')) if lower == upper and len(ans) < j - i + 1: ans = s[i : j + 1] return ans -
func longestNiceSubstring(s string) string { n := len(s) k, mx := -1, 0 for i := 0; i < n; i++ { ss := map[byte]bool{} for j := i; j < n; j++ { ss[s[j]] = true ok := true for a := range ss { b := a ^ 32 if !(ss[a] && ss[b]) { ok = false break } } if ok && mx < j-i+1 { mx = j - i + 1 k = i } } } if k < 0 { return "" } return s[k : k+mx] } // Solution 2 func longestNiceSubstring(s string) string { n := len(s) k, mx := -1, 0 for i := 0; i < n; i++ { var lower, upper int for j := i; j < n; j++ { if unicode.IsLower(rune(s[j])) { lower |= 1 << (s[j] - 'a') } else { upper |= 1 << (s[j] - 'A') } if lower == upper && mx < j-i+1 { mx = j - i + 1 k = i } } } if k < 0 { return "" } return s[k : k+mx] } -
function longestNiceSubstring(s: string): string { const n = s.length; let ans = ''; for (let i = 0; i < n; i++) { let lower = 0, upper = 0; for (let j = i; j < n; j++) { const c = s.charCodeAt(j); if (c > 96) { lower |= 1 << (c - 97); } else { upper |= 1 << (c - 65); } if (lower == upper && j - i + 1 > ans.length) { ans = s.substring(i, j + 1); } } } return ans; }