Longest Nice Substring
|
|
This function, longestNiceSubstring
, determines the longest nice substring within a given string s
. A “nice” substring is one where for every character that is in the substring, the substring also contains its uppercase and lowercase versions.
Here’s a breakdown of how this function works:
If the length of the input string
s
is less than 2, it immediately returns an empty string. This is because a nice string requires at least one pair of uppercase and lowercase letters.The function then converts the string
s
into a listarr
and a set_set
. The purpose of the set is to allow quick lookups of characters in the string.The function iterates over each character
c
inarr
. For each character, it checks if both the uppercase and lowercase versions of the character exist in_set
. If they do, it moves on to the next character.If either the uppercase or lowercase version of
c
is not in_set
, it meanss
is not a nice string. The function then splitss
into two substrings at the current indexi
and makes recursive calls tolongestNiceSubstring
on these substrings.The function compares the lengths of the two resulting substrings
sub1
andsub2
and returns the longer one. If their lengths are equal, it returnssub1
.If the function reaches the end of the string without finding a character that lacks its uppercase or lowercase version, it means
s
is a nice string. So it returnss
.
This function employs a divide-and-conquer strategy. When it finds a character that’s not nice, it divides the problem into two smaller problems (the substrings before and after that character) and solves them recursively.