{"id":8127,"date":"2021-02-20T15:29:06","date_gmt":"2021-02-20T23:29:06","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8127"},"modified":"2021-02-20T15:29:44","modified_gmt":"2021-02-20T23:29:44","slug":"leetcode-1763-longest-nice-substring","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-1763-longest-nice-substring\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1763. Longest Nice Substring"},"content":{"rendered":"\n

A string s<\/code> is nice<\/strong> if, for every letter of the alphabet that s<\/code> contains, it appears both<\/strong> in uppercase and lowercase. For example, \"abABB\"<\/code> is nice because 'A'<\/code> and 'a'<\/code> appear, and 'B'<\/code> and 'b'<\/code> appear. However, \"abA\"<\/code> is not because 'b'<\/code> appears, but 'B'<\/code> does not.<\/p>\n\n\n\n

Given a string s<\/code>, return the longest substring<\/strong> of s<\/code> that is nice<\/strong>. If there are multiple, return the substring of the earliest<\/strong> occurrence. If there are none, return an empty string<\/em>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> s = \"YazaAay\"\nOutput:<\/strong> \"aAa\"\nExplanation: <\/strong>\"aAa\" is a nice string because 'A\/a' is the only letter of the alphabet in s, and both 'A' and 'a' appear.\n\"aAa\" is the longest nice substring.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> s = \"Bb\"\nOutput:<\/strong> \"Bb\"\nExplanation:<\/strong> \"Bb\" is a nice string because both 'B' and 'b' appear. The whole string is a substring.<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> s = \"c\"\nOutput:<\/strong> \"\"\nExplanation:<\/strong> There are no nice substrings.<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
Input:<\/strong> s = \"dDzeE\"\nOutput:<\/strong> \"dD\"\nExplanation: <\/strong>Both \"dD\" and \"eE\" are the longest nice substrings.\nAs there are multiple longest nice substrings, return \"dD\" since it occurs earlier.<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= s.length <= 100<\/code><\/li>
  • s<\/code> consists of uppercase and lowercase English letters.<\/li><\/ul>\n\n\n\n
    <\/p>\n\n\n\n
    Solution: Brute Force<\/strong><\/h2>\n\n\n\n
    Time complexity: O(n^3)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \nclass Solution {\npublic:\n  string longestNiceSubstring(string_view s) {    \n    const int n = s.length();\n    auto isNice = [](string_view s) {\n      vector u(26), l(26);\n      for (int c : s)\n        if (isupper(c)) u[c - 'A'] = 1;\n        else l[c - 'a'] = 1;\n      return u == l;\n    };\n    string_view ans;    \n    for (int i = 0; i < n; ++i)\n      for (int j = i + 1; j < n; ++j) {\n        string_view ss = s.substr(i, j - i + 1);\n        if (isNice(ss) && ss.length() > ans.length())\n          ans = ss;\n      }\n    return string(ans);\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
    Optimized 1: <\/p>\n\n\n\n
    Time complexity: O(n^2*26)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \nclass Solution {\npublic:\n  string longestNiceSubstring(string_view s) {    \n    const int n = s.length();    \n    string_view ans;\n    for (int i = 0; i < n; ++i) {\n      vector u(26), l(26);\n      for (int j = i; j < n; ++j) {\n        const char c = s[j];\n        if (isupper(c)) u[c - 'A'] = 1;\n        else l[c - 'a'] = 1;\n        if (u == l && j - i + 1 > ans.length())\n          ans = s.substr(i, j - i + 1);\n      }\n    }\n    return string(ans);\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
    <\/p>\n","protected":false},"excerpt":{"rendered":"
    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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[47],"tags":[222,4],"class_list":["post-8127","post","type-post","status-publish","format-standard","hentry","category-string","tag-easy","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8127","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8127"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8127\/revisions"}],"predecessor-version":[{"id":8129,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8127\/revisions\/8129"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8127"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8127"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8127"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}