Problem Description

A string is considered nice if every letter that appears in the string has both its uppercase and lowercase versions present in the string.

For example:

• "abABB" is nice because:
  • Letter 'a' appears as both 'a' and 'A'
  • Letter 'b' appears as both 'b' and 'B'
• "abA" is NOT nice because:
  • Letter 'b' appears only in lowercase (no 'B')
  • Even though 'a' has both cases, the presence of 'b' without 'B' makes it not nice

Given a string s, you need to find the longest substring that is nice. A substring is a contiguous sequence of characters within the string.

Important constraints:

• If multiple substrings have the same maximum length, return the one that appears earliest in the string
• If no nice substring exists, return an empty string

The solution uses a brute force approach by checking all possible substrings. For each starting position i, it extends to position j and maintains a set of characters seen so far. At each extension, it checks if all characters in the current substring have both their uppercase and lowercase versions present. If this condition is met and the current substring is longer than the previously found answer, it updates the answer.

The key insight in the checking logic is that for a substring to be nice, every character c in the substring must have both c.lower() and c.upper() present in the character set of that substring.

Intuition

The first observation is that we need to check substrings, not subsequences. This means we're looking at continuous portions of the string. Since we want the longest nice substring, we need to examine all possible substrings and keep track of the longest one that satisfies our "nice" condition.

The brute force approach becomes natural here - we can generate all possible substrings by using two nested loops: one for the starting position and one for the ending position. This gives us all substrings of the form s[i:j+1].

For checking if a substring is "nice", we need to verify that every letter present has both its cases. A clever way to do this is to maintain a set of all characters in the current substring. Then, for each character in this set, we check if both its lowercase and uppercase versions exist in the same set.

Why use a set? Because:

1. It automatically handles duplicates (we only care about which characters are present, not how many times)
2. Membership checking (in operation) is O(1), making our validation efficient

The checking condition all(c.lower() in ss and c.upper() in ss for c in ss) elegantly handles all cases:

• If c is lowercase, it checks if both c (itself) and c.upper() are in the set
• If c is uppercase, it checks if both c.lower() and c (itself) are in the set
• This works correctly regardless of whether we encounter the uppercase or lowercase version first

Since we iterate from left to right (starting position i from 0 to n-1), we naturally get the earliest occurrence when multiple substrings have the same maximum length. We only update our answer when we find a strictly longer nice substring, ensuring we keep the first one of any given length.

Learn more about Divide and Conquer and Sliding Window patterns.

Solution Approach

The implementation uses a nested loop approach to examine all possible substrings:

1. Outer Loop (Starting Position): Iterate through each index i from 0 to n-1 as the starting position of potential substrings.

2. Initialize Character Set: For each starting position, create an empty set ss to store the characters encountered in the current substring.

3. Inner Loop (Ending Position): For each starting position i, iterate through indices j from i to n-1 as ending positions:

   • Add the character at position j to the set: ss.add(s[j])
   • This incrementally builds up the character set for substring s[i:j+1]

4. Check Nice Condition: After adding each new character, verify if the current substring is nice:

   • Use all(c.lower() in ss and c.upper() in ss for c in ss) to check if every character in the set has both its uppercase and lowercase versions present
   • This condition iterates through each unique character c in the set and ensures both cases exist

5. Update Answer: If the substring is nice AND its length (j - i + 1) is greater than the current answer's length:

   • Update ans to the current substring: ans = s[i : j + 1]
   • The condition len(ans) < j - i + 1 ensures we only update for strictly longer substrings
   • Since we iterate from left to right, this naturally preserves the earliest occurrence

6. Return Result: After checking all possible substrings, return ans (which remains empty string if no nice substring was found).

Time Complexity: O(n² × m) where n is the length of the string and m is the size of the character set (at most 52 for all uppercase and lowercase letters). The nested loops give us O(n²) substrings, and for each substring, we verify the nice condition which takes O(m) time.

Space Complexity: O(m) for the character set, where m is at most 52 characters.

Example Walkthrough

Let's walk through the solution with the string s = "YazaAay".

Goal: Find the longest nice substring where every letter has both uppercase and lowercase versions.

Step-by-step process:

Starting with i = 0 (starting at 'Y'):

• j = 0: substring = "Y", set = {'Y'}
  • Check: Does 'Y' have both cases? Need 'Y' ✓ and 'y' ✗ → Not nice
• j = 1: substring = "Ya", set = {'Y', 'a'}
  • Check: 'Y' needs 'y' ✗, 'a' needs 'A' ✗ → Not nice
• j = 2: substring = "Yaz", set = {'Y', 'a', 'z'}
  • Check: 'Y' needs 'y' ✗, 'a' needs 'A' ✗, 'z' needs 'Z' ✗ → Not nice
• j = 3: substring = "Yaza", set = {'Y', 'a', 'z'}
  • Check: Same as above → Not nice
• j = 4: substring = "YazaA", set = {'Y', 'a', 'z', 'A'}
  • Check: 'Y' needs 'y' ✗, 'a' has 'A' ✓, 'z' needs 'Z' ✗ → Not nice
• j = 5: substring = "YazaAa", set = {'Y', 'a', 'z', 'A'}
  • Check: Same as above → Not nice
• j = 6: substring = "YazaAay", set = {'Y', 'a', 'z', 'A', 'y'}
  • Check: 'Y' has 'y' ✓, 'a' has 'A' ✓, 'z' needs 'Z' ✗ → Not nice

Starting with i = 1 (starting at 'a'):

• j = 1: substring = "a", set = {'a'}
  • Check: 'a' needs 'A' ✗ → Not nice
• j = 2: substring = "az", set = {'a', 'z'}
  • Check: 'a' needs 'A' ✗, 'z' needs 'Z' ✗ → Not nice
• j = 3: substring = "aza", set = {'a', 'z'}
  • Check: Same as above → Not nice
• j = 4: substring = "azaA", set = {'a', 'z', 'A'}
  • Check: 'a' has 'A' ✓, 'z' needs 'Z' ✗ → Not nice
• j = 5: substring = "azaAa", set = {'a', 'z', 'A'}
  • Check: Same as above → Not nice
• j = 6: substring = "azaAay", set = {'a', 'z', 'A', 'y'}
  • Check: 'a' has 'A' ✓, 'z' needs 'Z' ✗, 'y' needs 'Y' ✗ → Not nice

Starting with i = 2 (starting at 'z'):

• j = 2: substring = "z", set = {'z'}
  • Check: 'z' needs 'Z' ✗ → Not nice
• Continue similarly...

Starting with i = 3 (starting at 'a'):

• j = 3: substring = "a", set = {'a'}
  • Check: 'a' needs 'A' ✗ → Not nice
• j = 4: substring = "aA", set = {'a', 'A'}
  • Check: 'a' has 'A' ✓, 'A' has 'a' ✓ → Nice!
  • Length = 2, update ans = "aA"
• j = 5: substring = "aAa", set = {'a', 'A'}
  • Check: 'a' has 'A' ✓, 'A' has 'a' ✓ → Nice!
  • Length = 3 > 2, update ans = "aAa"
• j = 6: substring = "aAay", set = {'a', 'A', 'y'}
  • Check: 'a' has 'A' ✓, 'A' has 'a' ✓, 'y' needs 'Y' ✗ → Not nice

Starting with i = 4 (starting at 'A'):

• j = 4: substring = "A", set = {'A'}
  • Check: 'A' needs 'a' ✗ → Not nice
• j = 5: substring = "Aa", set = {'A', 'a'}
  • Check: 'A' has 'a' ✓, 'a' has 'A' ✓ → Nice!
  • Length = 2 < 3 (current answer length), don't update
• j = 6: substring = "Aay", set = {'A', 'a', 'y'}
  • Check: 'y' needs 'Y' ✗ → Not nice

Starting with i = 5 and i = 6 find no nice substrings or none longer than 3.

Final answer: "aAa" - the longest nice substring with length 3.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²)

The algorithm uses two nested loops:

• The outer loop runs from i = 0 to n-1, iterating n times
• The inner loop runs from j = i to n-1, iterating up to n times in the worst case
• Inside the inner loop, the all() function checks each character in the set ss, which can contain at most 52 unique characters (26 lowercase + 26 uppercase letters), making this check O(1) since it's bounded by a constant
• String slicing s[i : j + 1] takes O(j - i + 1) time, but this only happens when a valid nice substring is found

Overall: O(n) × O(n) × O(1) = O(n²)

Space Complexity: O(1)

• The set ss stores unique characters from the current substring, which can contain at most 52 characters (all uppercase and lowercase English letters), so it uses O(1) space
• The variable ans stores the result string, which in the worst case could be the entire input string of length n, contributing O(n) space
• Other variables (i, j, n) use constant space

Since the output string is typically not counted towards space complexity (as it's required for the answer), the auxiliary space complexity is O(1).

If we count the output string, the space complexity would be O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Inefficient Character Set Building

A common mistake is rebuilding the character set from scratch for each substring instead of incrementally adding characters. This would change the time complexity from O(n²) to O(n³).

Incorrect approach:

for start in range(n):
    for end in range(start, n):
        # Wrong: Rebuilding set every time
        char_set = set(s[start:end+1])
        is_nice = all(...)

Correct approach:

for start in range(n):
    char_set = set()  # Initialize once per starting position
    for end in range(start, n):
        char_set.add(s[end])  # Incrementally build the set
        is_nice = all(...)

2. Incorrect Nice Condition Check

A frequent error is checking if both cases exist in the original string rather than in the current substring's character set.

Incorrect:

# Wrong: Checking in the entire string s
is_nice = all(char.lower() in s and char.upper() in s for char in char_set)

Correct:

# Right: Checking within the current substring's character set
is_nice = all(char.lower() in char_set and char.upper() in char_set for char in char_set)

3. Using <= Instead of < for Length Comparison

Using <= would update the result even for equal-length substrings, potentially returning a later occurrence instead of the earliest one.

Incorrect:

if is_nice and len(result) <= current_length:  # Wrong: Returns last occurrence
    result = s[start:end + 1]

Correct:

if is_nice and len(result) < current_length:  # Right: Returns first occurrence
    result = s[start:end + 1]

4. Mishandling Edge Cases

Forgetting to handle empty strings or single-character strings properly. The solution should naturally return an empty string for these cases since a single character cannot have both uppercase and lowercase versions present.

Solution: The current implementation handles this correctly by initializing result = '' and only updating when a valid nice substring is found.