# 1763. Longest Nice Substring¶

• Time: $O(n\log n) \to O(n^2)$
• Space: $O(n\log n) \to O(n^2)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { public: string longestNiceSubstring(string s) { if (s.length() < 2) return ""; unordered_set seen{s.begin(), s.end()}; for (int i = 0; i < s.size(); ++i) // If both upper and lower case letters exists in the string, keep moving, // else take the erroneous character as a partition and check for its left // and right parts to be nice strings. if (!seen.contains(toggleCase(s[i]))) { const string prefix = longestNiceSubstring(s.substr(0, i)); const string suffix = longestNiceSubstring(s.substr(i + 1)); return prefix.length() >= suffix.length() ? prefix : suffix; } return s; } private: char toggleCase(char c) { return islower(c) ? toupper(c) : tolower(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 s) { if (s.length() < 2) return ""; Set seen = s.chars().mapToObj(c -> (char) c).collect(Collectors.toSet()); for (int i = 0; i < s.length(); ++i) if (!seen.contains(toggleCase(s.charAt(i)))) { final String prefix = longestNiceSubstring(s.substring(0, i)); final String suffix = longestNiceSubstring(s.substring(i + 1)); return prefix.length() >= suffix.length() ? prefix : suffix; } return s; } private char toggleCase(char c) { return Character.isLowerCase(c) ? Character.toUpperCase(c) : Character.toLowerCase(c); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution: def longestNiceSubstring(self, s: str) -> str: if len(s) < 2: return '' seen = set(s) for i, c in enumerate(s): # If both upper and lower case letters exists in the string, keep moving, # else take the erroneous character as a partition and check for its left # and right parts to be nice strings. if c.swapcase() not in seen: prefix = self.longestNiceSubstring(s[:i]) suffix = self.longestNiceSubstring(s[i + 1:]) return max(prefix, suffix, key=len) return s