# When a string s The uppercase and lowercase forms of each letter contained meanwhile Appear in the s in , Just call this string s yes happy character string . For example ,"abABB" It's a beautiful string , because
# 'A' and 'a' At the same time , And 'B' and 'b' At the same time . However ,"abA" Not because 'b' There is , and 'B' There was no .
#
# Give you a string s , Please return s Longest Nice substring . If there are multiple answers , Please return Earliest The one that appears . If there is no good substring , Please return an empty string .
#
#
#
# Example 1：
#
#
# Input ：s = "YazaAay"
# Output ："aAa"
# explain ："aAa" It's a beautiful string , Because there is only one letter in this substring , Its lowercase form 'a' And capital form 'A' At the same time .
# "aAa" Is the longest nice substring .
#
#
# Example 2：
#
#
# Input ：s = "Bb"
# Output ："Bb"
# explain ："Bb" It's a beautiful string , because 'B' and 'b' There were . The whole string is also a substring of the original string .
#
# Example 3：
#
#
# Input ：s = "c"
# Output ：""
# explain ： No nice substring .
#
# Example 4：
#
#
# Input ：s = "dDzeE"
# Output ："dD"
# explain ："dD" and "eE" They're all the longest substrings .
# Because there are many nice substrings , return "dD" , Because it first appeared .
#
#
#
# Tips ：
#
#
# 1 <= s.length <= 100
# s Only upper and lower case letters .
#
# Related Topics An operation Hashtable character string The sliding window 75 0
Find all letters that do not meet the requirements , Take them as the dividing points , Break the source string into substrings , Find the longest of all substrings that meet the requirements .
# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
def longestNiceSubstring(self, s: str) -> str:
max_len = 0
ret = ""
def check(str_list):
nonlocal max_len, ret
for s in str_list:
if len(s) > 1:
s_set = set(s)
split_pos = []
for i in range(len(s)):
if s[i].lower() not in s_set or s[i].upper() not in s_set:
split_pos.append(i)
if not split_pos:
if len(s) > max_len:
ret = s
max_len = len(s)
return
new_str_list = []
last_i = 0
for pos in split_pos:
new_str_list.append(s[last_i: pos])
last_i = pos + 1
if last_i < len(s): # Exclude the last one that is the split point
new_str_list.append(s[last_i:])
check(new_str_list)
str_list = [s]
check(str_list)
return ret
# leetcode submit region end(Prohibit modification and deletion)
class Solution:
def longestNiceSubstring(self, s: str) -> str:
if len(s) < 2:
return ""
for i, c in enumerate(s):
# There are any cut points that do not satisfy the problem
if c.upper() not in s or c.lower() not in s:
return max(self.longestNiceSubstring(s[:i]), self.longestNiceSubstring(s[i+1:]), key = len)
return s
author ：himymBen
link ：https://leetcode-cn.com/problems/longest-nice-substring/solution/pythonjavajavascriptgo-by-himymben-rbx7/
source ： Power button （LeetCode）
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .
