1763. Longest Nice Substring

1763. Longest Nice Substring (Easy)

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.

Related Topics:
String

Solution 1. Brute force

// OJ: https://leetcode.com/problems/longest-nice-substring/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(N)
class Solution {
    bool nice(string &s) {
        int up[26] = {}, low[26] = {};
        for (char c : s) {
            if (c >= 'A' && c <= 'Z') up[c - 'A'] = 1;
            else low[c - 'a'] = 1;
        }
        for (int i = 0; i < 26; ++i) {
            if (up[i] ^ low[i]) return false;
        }
        return true;
    }
public:
    string longestNiceSubstring(string s) {
        int N = s.size();
        for (int len = N; len >= 2; --len) {
            for (int i = 0; i <= N - len; ++i) {
                auto sub = s.substr(i, len);
                if (nice(sub)) return sub;
            }
        }
        return "";
    }
};

Solution 2. Divide and Conquer

Time complexity

The depth of the recursion is at most 26 levels, each of which we use a letter to split the windows.

In each recursion, we traverse the string in O(N) time. Even though we take substring, each letter is at most copied once, so overall each recursion is still O(N).

So the overall time complexity is O(26N) = O(N).

// OJ: https://leetcode.com/problems/longest-nice-substring/
// Author: github.com/lzl124631x
// Time: O(N), the depth of the recursion is at most 26.
// Space: O(N)
class Solution {
    string ans;
public:
    string longestNiceSubstring(string s) {
        int state[26] = {};
        for (char c : s) {
            if (isupper(c)) state[c - 'A'] |= 2;
            else state[c - 'a'] |= 1;
        }
        int i = 0, N = s.size();
        while (i < N) {
            int j = i;
            while (j < N && state[tolower(s[j]) - 'a'] == 3) ++j; // find the window only contain characters that in state 3, i.e. having both upper and lower case
            int len = j - i;
            if (len == N) { // this string itself is nice, update the answer
                ans = s;
                break;
            }
            if (len > ans.size()) longestNiceSubstring(s.substr(i, len)); // handle this window recursively. The recursion is at most 26 levels.
            while (j < N && state[tolower(s[j]) - 'a'] != 3) ++j;
            i = j;
        } 
        return ans;
    }
};