LeetCode 1763 - Longest Nice Substring

Difficulty: 🟢 Easy
Topics: Hash Table, String, Divide and Conquer, Bit Manipulation, Sliding Window

Solution

Problem Understanding

The problem asks us to find the longest "nice" substring within a given string s. A substring is considered nice if for every letter it contains, both its lowercase and uppercase forms appear. For example, "aAa" is nice because it contains 'a' and 'A'. Conversely, "abA" is not nice because 'b' appears but 'B' does not. The input string s consists of only English letters and has a length between 1 and 100. The output should be the longest nice substring, and if there are multiple candidates of equal length, the earliest one should be returned. If no nice substring exists, an empty string should be returned.

Key points include the need to check case correspondence for all letters in a substring and to handle small strings efficiently. Edge cases include strings of length 1 (always not nice), strings with all letters in one case, and strings that are already entirely nice.

Approaches

The brute-force approach involves checking all possible substrings of s. For each substring, we would count its letters and verify that each letter has both its uppercase and lowercase forms present. While this guarantees correctness, it is inefficient because there are O(n²) substrings, and checking each substring can take O(n) time, resulting in O(n³) complexity.

The optimal approach leverages a divide-and-conquer strategy. The key insight is that if a substring contains a character whose opposite case is missing in the substring, that character cannot be part of any nice substring. Thus, we can split the string at such characters and recursively search the left and right substrings. This reduces unnecessary checks and efficiently finds the longest nice substring.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(n)	Check all substrings and validate if nice
Optimal	O(n²)	O(n)	Divide-and-conquer using characters missing opposite case

Algorithm Walkthrough

Define a helper function that takes a substring as input.
Convert the substring into a set of characters to efficiently check for missing opposite cases.
Iterate over the substring. For each character, check if its opposite case exists in the set.
If all characters have their opposite case, return the substring immediately as it is nice.
If a character is missing its opposite case, split the string at that character into left and right substrings.
Recursively call the helper function on the left and right substrings to find the longest nice substring in each.
Compare the results from left and right, and return the one with the greater length. If lengths are equal, return the left substring (earlier occurrence).
Start the recursion with the entire string s.

Why it works: The algorithm works because any character without its opposite case cannot be part of a nice substring. By splitting at these characters, we ensure that all remaining candidates in the recursion could potentially be nice. This divide-and-conquer property guarantees we eventually check all valid candidates without redundant computation.

Python Solution

class Solution:
    def longestNiceSubstring(self, s: str) -> str:
        def helper(sub: str) -> str:
            if len(sub) < 2:
                return ""
            chars = set(sub)
            for i, c in enumerate(sub):
                if c.swapcase() not in chars:
                    left = helper(sub[:i])
                    right = helper(sub[i+1:])
                    return left if len(left) >= len(right) else right
            return sub
        
        return helper(s)

Implementation walkthrough: The helper function checks if a substring is nice by converting it into a set of characters. For each character, it verifies the presence of its opposite case using c.swapcase(). If a mismatch is found, it splits the substring into left and right and recursively finds the longest nice substring. The recursion ensures that all candidates are explored efficiently.

Go Solution

func longestNiceSubstring(s string) string {
    var helper func(sub string) string
    helper = func(sub string) string {
        if len(sub) < 2 {
            return ""
        }
        chars := make(map[rune]bool)
        for _, c := range sub {
            chars[c] = true
        }
        for i, c := range sub {
            if !chars[rune(swapcase(byte(c)))] {
                left := helper(sub[:i])
                right := helper(sub[i+1:])
                if len(left) >= len(right) {
                    return left
                } else {
                    return right
                }
            }
        }
        return sub
    }
    
    return helper(s)
}

func swapcase(c byte) byte {
    if 'a' <= c && c <= 'z' {
        return c - 'a' + 'A'
    } else if 'A' <= c && c <= 'Z' {
        return c - 'A' + 'a'
    }
    return c
}

Go-specific notes: We use a map[rune]bool to efficiently track characters. The swapcase function converts a letter from uppercase to lowercase and vice versa. Slices are used for substring extraction. The recursion logic mirrors Python closely.

Worked Examples

Example 1: s = "YazaAay"

Step	Substring	Set	Split or Return
initial	"YazaAay"	{Y,a,z,A,y}	'Y' missing 'y', split at index 0
left	""	{}	return ""
right	"azaAay"	{a,z,A,y}	'z' missing 'Z', split at index 1
left	"a"	{a}	length < 2, return ""
right	"aAay"	{a,A,y}	all characters have opposite, return "aAa"

Example 2: s = "Bb"

Step	Substring	Set	Split or Return
initial	"Bb"	{B,b}	all have opposite, return "Bb"

Example 3: s = "c"

Step	Substring	Set	Split or Return
initial	"c"	{c}	length < 2, return ""

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Each split checks the substring set, iterating over n characters. In the worst case, there could be n recursive calls.
Space	O(n)	Recursion stack depth can go up to n and we store sets of size up to n.

The divide-and-conquer approach avoids O(n³) by eliminating substrings that cannot be nice due to missing opposite-case characters.

Test Cases

# Provided examples
assert Solution().longestNiceSubstring("YazaAay") == "aAa"  # longest nice substring
assert Solution().longestNiceSubstring("Bb") == "Bb"        # entire string is nice
assert Solution().longestNiceSubstring("c") == ""           # no nice substring

# Edge and boundary cases
assert Solution().longestNiceSubstring("aA") == "aA"        # smallest nice substring
assert Solution().longestNiceSubstring("abAB") == "abAB"    # whole string is nice
assert Solution().longestNiceSubstring("abcd") == ""        # no nice substring
assert Solution().longestNiceSubstring("aAbBcCdD") == "aAbBcCdD" # all letters nice
assert Solution().longestNiceSubstring("aAaBbB") == "aAaBbB" # multiple nice substrings, full string is longest
assert Solution().longestNiceSubstring("AaBbC") == "AaBb"   # 'C' breaks niceness

Test	Why
"YazaAay"	Typical case, split required
"Bb"	Smallest nice string
"c"	No nice substring exists
"aA"	Minimum size substring that is nice
"abAB"	Entire string is nice
"abcd"	No uppercase letters, should return empty
"aAbBcCdD"	All letters appear nicely
"AaBbC"	Last letter breaks niceness, test earliest occurrence

Edge Cases

Single-character strings: Strings like "c" or "A" are not nice by definition, because they lack the opposite case. The implementation handles this by returning an empty string when the length is less than 2.

Strings with multiple splits: A string such as "YazaAay" requires multiple recursive splits at characters missing their opposite case. The recursion ensures all segments are considered, returning the longest nice substring among them.

Full string already nice: For strings like "aAbBcCdD", no splits occur because every character has its opposite case. The algorithm correctly identifies the whole string as the longest nice substring.

This careful handling ensures the algorithm is robust for a variety of scenarios while remaining efficient.