Longest Nice Substring
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 'b' without a 'B' (or the reverse) disqualifies the entire substring.
Two facts shape the solutions. The string is short (at most 100 characters), so a brute-force scan over all substrings is fast enough. And if a character in the string has no counterpart anywhere, it can never be part of a nice substring. That character splits the string into two halves, and the answer must lie entirely within one of them. That property leads to a divide and conquer approach.
Key Constraints:
1 <= s.length <= 100→ With n at most 100, an O(n^3) brute force runs in about 10^6 operations, within time limits. A more efficient solution is optional, not required.s consists of uppercase and lowercase English letters→ At most 52 distinct characters (26 lowercase, 26 uppercase). A 26-bit mask per case is enough to track which letters appear.
Approach 1: Brute Force
Intuition
Check every possible substring and test whether it is nice. For each substring, collect its characters into a set, then verify that every character in the set has its case counterpart in the set as well.
With n at most 100, there are about 5,000 substrings, and testing each one takes O(n) time. That is roughly 500,000 operations.
We want the longest nice substring, breaking ties toward the earliest one. We track the best length and its starting position as we scan, and only update when we find a strictly longer substring, so the earliest of two equal-length results is kept.
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 test all substrings. Any substring that includes index 0 ('Y') has no 'y' until index 6, and any substring that spans index 2 ('z') contains a 'z' with no 'Z', so none of those are nice. The nice substrings all sit between index 3 and index 5. The substring "aA" (indices 3-4) is nice because both 'a' and 'A' are present. Extending to "aAa" (indices 3-5) stays nice. Extending to "aAay" (indices 3-6) adds 'y' without 'Y', so it is not nice. No substring of length 4 or more is nice, so the best is "aAa" with length 3, recorded the first time it appears.
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 checks every substring independently, including ones that contain a character with no counterpart, which can never be nice. The next approach uses those characters to split the string and avoid that wasted work.
Approach 2: Divide and Conquer
Intuition
If a character appears in the string but its case counterpart does not, that character can never be part of any nice substring. Any nice substring must lie entirely on one side of it.
That gives a recursive strategy. Scan the string for a character whose counterpart is missing, split the string at that character, and recursively find the longest nice substring in each piece. The answer is the longest result across the pieces.
When every character in a piece has its counterpart present, that piece is itself nice and we return it unchanged. That is the base case.
A character without its case counterpart in the full string cannot appear in any nice substring of that string, since a nice substring containing it would also lack the counterpart. So splitting at that character drops no candidate answers. Every nice substring lies entirely within one of the two pieces, and recursion finds the longest one in each.
The tie-break is handled by the >= comparison: when the left and right results are equal in length, it returns the left, which starts at an earlier index in the original string. That matches the requirement to return the earliest of equal-length answers.
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^2) worst case. Each recursion level scans its string in O(n) and builds a set. Every split removes at least one distinct character (the unpaired one), so the recursion depth is at most the number of distinct characters, which is bounded by 52. With n much larger than 52 the depth is effectively constant, but the worst case (a string of distinct unpaired characters forcing a split at each step) is O(n^2).
- Space Complexity: O(n) for the set and substring copies at each level, times a recursion depth bounded by 52.
Divide and conquer creates substring copies at each recursion level. The next approach drops the recursion and the set, checking all substrings iteratively while reducing the niceness test to a single integer comparison.
Approach 3: Bitmask Optimization
Intuition
Represent character presence with two 26-bit masks: lowerMask for lowercase letters and upperMask for uppercase letters. Bit 0 stands for a/A, bit 1 for b/B, and so on.
For a substring starting at a fixed index, extend the end one character at a time and update the masks. The substring is nice when lowerMask == upperMask, since matching bits mean every lowercase letter that appears has its uppercase counterpart and the reverse.
This checks all substrings like the brute force, but the niceness test is a single comparison of two integers instead of a scan over a set. The asymptotic cost stays O(n^2), with a much smaller constant factor.
Bit k of lowerMask is set when the (k+1)-th lowercase letter has appeared in the substring, and bit k of upperMask when the matching uppercase letter has appeared. The two masks are equal exactly when, for every letter position, either both cases appeared or neither did. That is the definition of nice. A single OR sets a bit when a character arrives, so each window extension is O(1) and the test is one equality check.
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.