Longest Nice Substring
Last Updated: March 29, 2026
Understanding the Problem
We need to find the longest substring where every letter that shows up has both its uppercase and lowercase versions present in that same substring. The word "substring" means a contiguous sequence of characters, not a subsequence.
What makes this different from simpler substring problems is the "both cases" constraint. It is not enough for a character to appear. Its counterpart must also be present. A single lonely 'b' without a 'B' (or vice versa) disqualifies the entire substring.
A couple of things to notice right away. First, the string is short (at most 100 characters), so even brute force approaches will work. Second, if a character in the string has no counterpart anywhere, it can never be part of a nice substring. That character effectively "breaks" the string, and the answer must lie entirely on one side of it. This observation opens the door to a divide and conquer approach.
Key Constraints:
1 <= s.length <= 100→ With n at most 100, even O(n^3) brute force runs in about 10^6 operations, well within time limits. There is no pressure to find a hyper-optimized solution.s consists of uppercase and lowercase English letters→ At most 52 distinct characters (26 lowercase + 26 uppercase). We can use fixed-size arrays or bitmasks to track character presence efficiently.
Approach 1: Brute Force
Intuition
The simplest approach is exactly what it sounds like: check every possible substring and see if it is nice. For each substring, collect all the characters into a set, then verify that for every character in the set, its case counterpart is also in the set.
With n at most 100, there are at most about 5,000 substrings, and checking each one takes at most O(n) time. That is roughly 500,000 operations, which is nothing for modern hardware.
We want the longest nice substring, and in case of ties, the earliest one. So we track the maximum length and the starting position as we go.
Algorithm
- Initialize variables to track the best starting index and best length found so far.
- For each starting index
ifrom 0 to n-1, iterate over ending indicesjfromi+1to n. - For the substring
s[i..j], collect all characters into a set. - Check if the substring is nice: for every character
cin the set, verify that both its uppercase and lowercase versions are in the set. - If the substring is nice and its length is greater than the current best, update the best.
- Return the best substring, or an empty string if none was found.
Example Walkthrough
Input:
We check all substrings. Starting at index 3, the substring "aA" (indices 3-4) is nice because both 'a' and 'A' are present. Extending to "aAa" (indices 3-5) is still nice. But extending further to "aAay" adds 'y' without 'Y', breaking niceness.
Result:
Code
- Time Complexity: O(n^3). There are O(n^2) substrings, and for each one we build a set and check niceness in O(n) time.
- Space Complexity: O(n). We create a substring and a set for each check. The set holds at most 52 characters, but the substring copy itself is O(n).
This approach works but checks every substring independently, even ones containing characters that can never be part of a nice substring. What if we could identify those "deal-breaker" characters and use them to split the problem into smaller pieces?
Approach 2: Divide and Conquer
Intuition
Here is the key insight: if a character appears in the string but its case counterpart does not, that character can never be part of any nice substring. It is a "deal-breaker." Any nice substring must lie entirely on one side of that character.
This gives us a natural recursive strategy. Scan the string and find any character whose counterpart is missing. Split the string at that character. Then recursively find the longest nice substring in each piece. The answer is the longest result across all pieces.
When we reach a string where every character has its counterpart present, the entire string is nice, and we return it as-is. This is our base case.
The correctness hinges on one observation: a character without its case counterpart in the full string can never appear in any nice substring of that string. So we lose nothing by splitting at that character. Every possible nice substring must be contained entirely within one of the resulting pieces.
By always splitting at the first bad character we find and recursing, we guarantee that we explore all viable segments. The >= comparison when choosing between left and right ensures we return the earliest result in case of ties, since the left piece always corresponds to an earlier position in the original string.
Algorithm
- If the string length is less than 2, return an empty string (a single character can never be nice).
- Build a set of all characters in the string.
- Scan through the string looking for any character whose case counterpart is not in the set.
- If no such character exists, the entire string is nice. Return it.
- If we find a "bad" character, split the string at that character.
- Recursively solve each piece.
- Return the longest result. In case of a tie, the earlier one wins.
Example Walkthrough
Code
- Time Complexity: O(n * 26) average, O(n^2) worst case. At each recursion level we scan the string in O(n). The recursion depth is bounded by 26 (one level per unique character pair eliminated), so average case is O(26n). Worst case with all unique unpaired characters gives O(n^2).
- Space Complexity: O(n). Each recursion level uses O(n) for the set and substring copies, with recursion depth at most 26.
The divide and conquer approach is elegant but creates substring copies at each recursion level. What if we could check all substrings without recursion, using bitmasks to make the niceness check a single integer comparison?
Approach 3: Bitmask Optimization
Intuition
Instead of using sets and recursion, we can represent character presence with two bitmasks: one for lowercase letters and one for uppercase letters. Each bit position corresponds to a letter (bit 0 = a/A, bit 1 = b/B, and so on).
For any substring, we maintain a lowerMask and an upperMask as we extend the window. The substring is nice when lowerMask == upperMask, meaning every lowercase letter that appears also has its uppercase counterpart, and vice versa.
This approach goes back to checking all substrings (like the brute force), but the niceness check becomes a single comparison of two integers instead of iterating through a set. This makes it significantly faster in practice, even though the asymptotic complexity is O(n^2).
Each bit in lowerMask represents "this lowercase letter has appeared in the substring." Each bit in upperMask represents "this uppercase letter has appeared." When the two masks are equal, every letter that appears in any case also appears in the other case. That is exactly the definition of nice.
The beauty of this approach is that extending the window by one character is just a single OR operation, and checking niceness is a single equality comparison. No sets, no iteration over characters, just two integers.
Algorithm
- Initialize variables to track the best starting index and best length.
- For each starting index
i, initialize two bitmasks to 0. - Extend the window by iterating
jfromiton-1. - For each character at position
j, set the appropriate bit inlowerMaskorupperMask. - If
lowerMask == upperMaskand the current window is longer than the best, update the best. - Return the best substring.
Example Walkthrough
Code
- Time Complexity: O(n^2). Two nested loops over the string. The inner work per iteration is O(1) thanks to bitmask operations.
- Space Complexity: O(1). Only a few integer variables. No extra data structures needed.