Longest Nice Substring
EasyPrompt
A string s is nice if, for every letter of the alphabet that s contains, it appears both in uppercase and lowercase. For example, "abABB" is nice because 'A' and 'a' appear, and 'B' and 'b' appear. However, "abA" is not because 'b' appears, but 'B' does not.
Given a string s, return the longest substring of s that is nice. If there are multiple, return the substring of the earliest occurrence. If there are none, return an empty string.
Example 1:
Input: s = "YazaAay"
Output: "aAa"
Explanation: "aAa" is a nice string because 'A/a' is the only letter of the alphabet in s, and both 'A' and 'a' appear.
"aAa" is the longest nice substring.Example 2:
Input: s = "Bb"
Output: "Bb"
Explanation: "Bb" is a nice string because both 'B' and 'b' appear. The whole string is a substring.Example 3:
Input: s = "c"
Output: ""
Explanation: There are no nice substrings.
Constraints:
1 <= s.length <= 100sconsists of uppercase and lowercase English letters.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach improves upon the brute-force method by optimizing the check for a "nice" substring. Instead of re-evaluating each substring from scratch, it maintains state as it expands a window. It iterates through all possible starting points and, for each, expands an ending point, efficiently checking for the "nice" property in O(1) time using bitmasks.
Algorithm
- Initialize
maxLen = 0andstartIdx = 0to track the longest nice substring found. - Use a nested loop structure. The outer loop with index
iiterates from0toN-1, fixing the starting position of a potential substring. - For each starting position
i, initialize two integer bitmasks,lowerMaskandupperMask, to zero. - The inner loop with index
jiterates fromitoN-1, extending the end of the current substring. - In the inner loop, for each character
c = s.charAt(j):- If
cis a lowercase letter, set the corresponding bit inlowerMask. (e.g., for 'c', set the 2nd bit:lowerMask |= (1 << ('c' - 'a'))). - If
cis an uppercase letter, set the corresponding bit inupperMask. (e.g., for 'C', set the 2nd bit:upperMask |= (1 << ('C' - 'A'))).
- If
- After updating the masks, check if
lowerMask == upperMask. This condition is true if and only if for every letter type present in the substrings[i..j], both its lowercase and uppercase forms have appeared. - If the condition is true and the current substring's length
(j - i + 1)is greater thanmaxLen, updatemaxLenandstartIdx. - After the loops complete, return the substring
s.substring(startIdx, startIdx + maxLen).
Walkthrough
The algorithm uses two nested loops to define a sliding window s[i..j]. The outer loop fixes the start i, and the inner loop iterates the end j from i to the end of the string.
For each window starting at i, we use two integer bitmasks, lowerMask and upperMask, to keep track of the lowercase and uppercase characters seen so far within that window. As j increases, we encounter a new character s[j] and update the appropriate bitmask. This is an O(1) operation.
A substring s[i..j] is nice if and only if for every character type present, both its lowercase and uppercase forms are present. This translates to a simple and extremely fast check: lowerMask == upperMask. If this condition is met, we have found a nice substring. We then check if its length (j - i + 1) is greater than the maximum length found so far and update our answer if it is.
class Solution { public String longestNiceSubstring(String s) { int n = s.length(); if (n < 2) { return ""; } int maxLen = 0; int startIdx = 0; for (int i = 0; i < n; i++) { int lowerMask = 0; int upperMask = 0; for (int j = i; j < n; j++) { char c = s.charAt(j); if (Character.isLowerCase(c)) { lowerMask |= (1 << (c - 'a')); } else { upperMask |= (1 << (c - 'A')); } if (lowerMask == upperMask) { if (j - i + 1 > maxLen) { maxLen = j - i + 1; startIdx = i; } } } } return s.substring(startIdx, startIdx + maxLen); }}Complexity
Time
O(N^2). The two nested loops iterate through all `O(N^2)` substrings. The operations inside the inner loop (bit manipulation, comparison) are constant time, O(1).
Space
O(1). We only use a few integer variables to store the masks and indices, regardless of the input string size. The space for the returned substring is not counted as part of the auxiliary space complexity.
Trade-offs
Pros
Optimal space complexity of O(1).
Time complexity of O(N^2) is efficient enough for the given constraints.
Iterative solution avoids recursion overhead, making it practically faster than the divide and conquer approach.
Cons
The time complexity is still O(N^2), which might be slow for very large N (though efficient enough for the given constraints).
The use of bitmasking might be slightly less intuitive than a direct character set comparison for some developers.
Solutions
Solution
class Solution {public String longestNiceSubstring(String s) { int n = s.length(); int k = -1; int mx = 0; for (int i = 0; i < n; ++i) { Set<Character> ss = new HashSet<>(); for (int j = i; j < n; ++j) { ss.add(s.charAt(j)); boolean ok = true; for (char a : ss) { char b = (char)(a ^ 32); if (!(ss.contains(a) && ss.contains(b))) { ok = false; break; } } if (ok && mx < j - i + 1) { mx = j - i + 1; k = i; } } } return k == -1 ? "" : s.substring(k, k + mx); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.