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.
This approach systematically checks every possible substring of the input string s. For each substring, it verifies if it meets the criteria of a "nice" string. The longest nice substring found is recorded and returned. This is the most straightforward but least efficient method.
Algorithm
- Initialize an empty string
longestNiceto store the result. - Use a pair of nested loops to generate every possible substring of the input string
s. The outer loop with indexidetermines the start of the substring, and the inner loop with indexjdetermines the end. - For each substring
sub, create a helper functionisNice(sub)to check if it's a nice string. - Inside
isNice(sub):- Create a
HashSetof all characters present insubfor efficient lookup. - Iterate through each character
cin the set. - For each
c, check if its case-swapped counterpart (e.g., 'a' for 'A', 'B' for 'b') is also present in the set. - If any character's counterpart is missing, the substring is not nice, so return
false. - If all characters have their counterparts, the substring is nice; return
true.
- Create a
- If
isNice(sub)returnstrueand the length ofsubis greater than the length oflongestNice, updatelongestNicetosub. - After checking all substrings, return
longestNice.
Walkthrough
The algorithm uses two nested loops to generate all substrings. The outer loop selects the starting index i, and the inner loop selects the ending index j. This results in O(N^2) substrings.
For each substring sub = s.substring(i, j + 1), a helper function isNice(sub) is called. The isNice function works by first creating a set of all unique characters in the substring, which takes time proportional to the substring's length. Then, it iterates through this set. For each character, it checks if its corresponding uppercase or lowercase counterpart is also present in the set. If any character's pair is missing, the substring is not nice. This check also takes time proportional to the substring's length.
If a substring is found to be nice and its length is greater than the length of the longest nice substring found so far, it becomes the new longest. Since we iterate through substrings starting from index 0, the first longest one we find will be the earliest, satisfying the tie-breaker rule.
import java.util.HashSet;import java.util.Set; class Solution { public String longestNiceSubstring(String s) { String longest = ""; for (int i = 0; i < s.length(); i++) { for (int j = i; j < s.length(); j++) { String sub = s.substring(i, j + 1); if (isNice(sub)) { if (sub.length() > longest.length()) { longest = sub; } } } } return longest; } private boolean isNice(String str) { Set<Character> charSet = new HashSet<>(); for (char c : str.toCharArray()) { charSet.add(c); } for (char c : charSet) { if (Character.isLowerCase(c)) { if (!charSet.contains(Character.toUpperCase(c))) { return false; } } else { // isUpperCase if (!charSet.contains(Character.toLowerCase(c))) { return false; } } } return true; }}Complexity
Time
O(N^3), where N is the length of the string. Generating all `O(N^2)` substrings, and for each substring of length `k`, the `isNice` check takes `O(k)` time. This leads to a total complexity of O(N^3).
Space
O(N), where N is the length of the string. This is for storing the character set for the longest possible substring. In practice, since the alphabet size is constant (52), the space for the set is O(1). The space for the result string can be up to O(N).
Trade-offs
Pros
Simple to understand and implement.
Correctly handles all cases and constraints.
Cons
Highly inefficient due to its cubic time complexity.
Performs redundant computations by re-evaluating overlapping substrings multiple times.
This approach is based on a key observation: if a character c exists in a string s but its case-counterpart does not, then c cannot be part of any nice substring. Such a character acts as a "splitter", dividing the problem into smaller, independent subproblems that can be solved recursively.
Algorithm
- Define a recursive function, let's call it
findNice(s). - Base Case: If the length of string
sis less than 2, it cannot be nice, so return an empty string"". - Recursive Step:
- Create a
HashSetcontaining all unique characters ofs. - Iterate through the string
swith an indexi. - For each character
cats[i], check if both its lowercase and uppercase versions are present in theHashSet. - If a character
cis found whose pair is missing, this character cannot be part of any nice substring. It acts as a 'splitter'. - Recursively call
findNiceon the substring to the left of the splitter (s.substring(0, i)) and the substring to the right (s.substring(i + 1)). - Compare the lengths of the results from the two recursive calls and return the longer one. If their lengths are equal, return the one from the left to satisfy the 'earliest occurrence' rule.
- Create a
- Success Case: If the loop completes without finding any splitter character, it means the entire string
sis nice. Returns.
Walkthrough
The core of this method is a recursive function that takes a string as input. First, it finds all unique characters in the current string segment and stores them in a set for quick lookups. Then, it iterates through the string segment. If it finds a character s[i] whose pair (e.g., a for A) is not in the set, it knows that s[i] cannot be in the result.
This "invalid" character at index i splits the string into two parts: the substring before i and the substring after i. The longest nice substring must lie entirely within one of these two parts. The algorithm then makes two recursive calls, one for the left part and one for the right part. It returns the longer of the two results. By prioritizing the left result in case of a tie, it correctly finds the earliest longest substring.
If the loop completes without finding any such "invalid" character, it means the entire current string segment is nice, and since we want the longest, we can return this segment itself.
import java.util.HashSet;import java.util.Set; class Solution { public String longestNiceSubstring(String s) { if (s.length() < 2) { return ""; } Set<Character> charSet = new HashSet<>(); for (char c : s.toCharArray()) { charSet.add(c); } for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (!charSet.contains(Character.toLowerCase(c)) || !charSet.contains(Character.toUpperCase(c))) { String s1 = longestNiceSubstring(s.substring(0, i)); String s2 = longestNiceSubstring(s.substring(i + 1)); return s1.length() >= s2.length() ? s1 : s2; } } return s; }}Complexity
Time
O(N^2) in the worst case. At each level of recursion, we scan the string segment of length `k`, taking `O(k)` time. The recursion depth can be up to `O(N)`, leading to a total time of `O(N^2)`. For balanced splits, it would be `O(N log N)`.
Space
O(N) in the worst case. This is due to the recursion stack depth, which can go up to N if the string is split one character at a time (e.g., `s = "abacada..."`).
Trade-offs
Pros
More efficient than the O(N^3) brute-force approach.
Provides an elegant recursive solution to the problem.
Often performs better than the worst-case, with an average time complexity closer to O(N log N) for balanced splits.
Cons
The worst-case time complexity is still O(N^2).
Recursion adds overhead and can lead to a deep recursion stack, consuming O(N) space in the worst case.
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); }}class Solution {public: string longestNiceSubstring(string s) { int n = s.size(); int k = -1, mx = 0; for (int i = 0; i < n; ++i) { unordered_set<char> ss; for (int j = i; j < n; ++j) { ss.insert(s[j]); bool ok = true; for (auto &a : ss) { char b = a ^ 32; if (!(ss.count(a) && ss.count(b))) { ok = false; break; } } if (ok && mx < j - i + 1) { mx = j - i + 1; k = i; } } } return k == -1 ? "" : s.substr(k, mx); }};class Solution: def longestNiceSubstring(self, s: str) -> str: n = len(s) ans = '' for i in range(n): ss = set() for j in range(i, n): ss . add(s[j]) if (all(c . lower() in ss and c . upper() in ss for c in ss) and len(ans) < j - i + 1): ans = s[i: j + 1] return ansVideo 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.