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 <= 100sconsists of uppercase and lowercase English letters.
Solution: Brute Force
Time complexity: O(n^3)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Solution { public: string longestNiceSubstring(string_view s) { const int n = s.length(); auto isNice = [](string_view s) { vector<int> u(26), l(26); for (int c : s) if (isupper(c)) u[c - 'A'] = 1; else l[c - 'a'] = 1; return u == l; }; string_view ans; for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) { string_view ss = s.substr(i, j - i + 1); if (isNice(ss) && ss.length() > ans.length()) ans = ss; } return string(ans); } }; |
Optimized 1:
Time complexity: O(n^2*26)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Solution { public: string longestNiceSubstring(string_view s) { const int n = s.length(); string_view ans; for (int i = 0; i < n; ++i) { vector<int> u(26), l(26); for (int j = i; j < n; ++j) { const char c = s[j]; if (isupper(c)) u[c - 'A'] = 1; else l[c - 'a'] = 1; if (u == l && j - i + 1 > ans.length()) ans = s.substr(i, j - i + 1); } } return string(ans); } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment