Longest Nice Substring

Longest Nice Substring

What is this problem about?

The Longest Nice Substring problem gives you a string s. A string is considered "nice" if, for every character in the string, both its uppercase and lowercase equivalents appear within the string. For example, "aAa" is nice because both 'a' and 'A' appear. "abA" is not nice because 'b' appears, but 'B' does not. Your task is to find the longest nice substring of s.

Why is this asked in interviews?

This is a popular entry-level String problem because it introduces candidates to the concept of Divide and Conquer. While it has an Easy rating and can be solved with a brute-force $O(N^2)$ sliding window, interviewers love to push candidates towards the more elegant recursive solution. It tests string parsing, hash set lookups, and recursive state management.

Algorithmic pattern used

The most elegant solution uses Divide and Conquer. You first put all characters of the current string into a Hash Set. Then, you iterate through the string. If you find a character whose upper or lower case counterpart is missing from the set, you know this character cannot possibly be part of any "nice" substring. Therefore, it acts as an invalid boundary. You split the string at this character and recursively call your function on the left part and the right part, returning the longest valid result.

Example explanation

Consider the string "YazaAay".

1. Set contains: Y, a, z, A, y.
2. We iterate:
   • Y: 'y' is in the set. Okay.
   • a: 'A' is in the set. Okay.
   • z: 'Z' is NOT in the set! This 'z' ruins everything.
3. We divide the string at 'z': Left is "Ya", Right is "aAay".
4. Process Left "Ya":
   • Set: Y, a.
   • Y lacks 'y'. Divide at 'Y'. Left "", Right "a". Both fail. "Ya" yields "".
5. Process Right "aAay":
   • Set: a, A, y.
   • a has 'A'. A has 'a'.
   • y lacks 'Y'. Divide at 'y'. Left "aAa", Right "".
6. Process "aAa":
   • Set: a, A. All characters have their pairs! It returns "aAa". The maximum nice substring is "aAa".

Common mistakes candidates make

A common mistake in the brute-force approach is creating complex nested loops with multiple maps that reset clumsily, leading to messy, bug-prone code. In the Divide and Conquer approach, candidates sometimes forget that if multiple substrings have the same maximum length, the problem usually requires returning the one that occurs first. You must use strict greater-than (>) when comparing left and right recursive results to preserve the earliest occurrence.

Interview preparation tip

When dealing with the Longest Nice Substring interview pattern, practice recognizing "invalid boundary" characters. If a string problem requires a global condition to be met (like all characters having pairs), finding a character that irreparably breaks that condition gives you a perfect pivot point to split the problem in half using Divide and Conquer.