Longest Nice Substring[Hash Table,String,Divide and Conquer,Bit Manipulation,Sliding Window]

https://leetcode.com/problems/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 <= 100
• s consists of uppercase and lowercase English letters.

1.Python

딴 건 모르겠고, Divide and conquer의 진면모를 볼 수 있었던 문제다.

그냥 Brute하게 if / else 문으로 도배를 해봤는데 fail...

역시 D and C.. 이해하긴 어렵지만, 코드 간단화에는 탁월한 녀석이다.

 

class Solution:
    def longestNiceSubstring(self, s: str) -> str:
        if len(s) == 1 :
            return ""
        
        for i in range(len(s)):
            if not (s[i].lower() in s and s[i].upper() in s):
                left = self.longestNiceSubstring(s[:i])
                right = self.longestNiceSubstring(s[i+1:])
                if len(right) > len(left) : return right
                else : return left
        return s

 

2. C++

#include <iostream>
#include <string>
#include <unordered_set>

using namespace std;

class Solution {
public:
    string longestNiceSubstring(string s) {
        if (s.length() < 2) {
            return "";
        }

        // Step 1: Check if the string contains a 'nice' character
        unordered_set<char> set(s.begin(), s.end());

        // Step 2: Iterate through the string and find where it's no longer 'nice'
        for (int i = 0; i < s.length(); ++i) {
            if (set.find(tolower(s[i])) == set.end() || set.find(toupper(s[i])) == set.end()) {
                // If the character is not part of a 'nice' pair, divide the string
                string left = longestNiceSubstring(s.substr(0, i));
                string right = longestNiceSubstring(s.substr(i + 1));

                // Return the longer of the two substrings
                return left.length() >= right.length() ? left : right;
            }
        }

        // If the whole string is nice, return the string
        return s;
    }
};

int main() {
    Solution sol;
    string input = "YazaAay";
    string result = sol.longestNiceSubstring(input);
    cout << "Longest nice substring: " << result << endl;  // Output: "aAa"
    return 0;
}

 

3. C

C는..생각치 말자.. 이런 유형의 문제에선..!