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 <= 100s consists of uppercase and lowercase English letters.Problem Overview: You are given a string s. A substring is considered nice if every letter in the substring appears in both lowercase and uppercase. For example, aA or bBccC are valid because each character has its opposite case present. The goal is to return the longest such substring. If multiple exist, return the earliest one.
Approach 1: Recursive Divide and Conquer (O(n^2) time, O(n) space)
This approach splits the problem around characters that violate the "nice" condition. First, scan the current substring and store its characters in a set (a common use of a hash table). If a character appears without its opposite case, that character can never be part of a valid nice substring. Use it as a split point. Recursively evaluate the left and right substrings around that character and return the longer result.
The key insight: a substring containing an invalid character cannot be nice, so dividing around it prunes the search space quickly. In practice, this dramatically reduces the number of checks. However, in the worst case—when many splits occur—the recursion can examine many substrings, giving O(n^2) time complexity and O(n) recursion stack space. This pattern is a classic divide and conquer strategy.
Approach 2: Sliding Window with Case Tracking (O(26 * n) time, O(1) space)
A more iterative solution uses the sliding window technique. Maintain a window with two counters: how many distinct lowercase letters and how many distinct uppercase letters are present. The window is "nice" only when every letter in the window has both forms present.
One practical trick is to iterate over the possible number of unique characters (1 to 26). For each target count, expand the window using two pointers and track lowercase/uppercase presence using arrays or a bit manipulation mask. When the window contains the desired number of unique characters and every character has both cases present, update the answer.
This keeps each character processed a constant number of times, leading to roughly O(26 * n) time, which simplifies to O(n). Space usage stays O(1) because the alphabet size is fixed.
Recommended for interviews: The divide-and-conquer approach is the most commonly discussed solution because the logic maps directly to the definition of a "nice" substring. It shows that you can identify invalid characters and partition the search space effectively. The sliding window variant demonstrates stronger optimization skills and familiarity with substring window patterns, which can stand out in interviews.
This approach involves recursively breaking the string at points where it is not nice. A character is considered problematic if its uppercase or lowercase counterpart does not exist in the string. The recursive division continues until an entire nice substring is found.
This Python solution defines two helper functions: is_nice to determine if a substring is nice and helper to recursively find the longest nice substring. It checks each character to see if its swapcase is in the string; if not, it splits the string and checks both halves. The function returns the longer substring.
Time Complexity: O(n^2 * 2^n) in the worst case due to recursive checks at each point.
Space Complexity: O(N) for the recursion stack.
This strategy uses a sliding window to limit the search space, checking each window to see if it is nice by maintaining a set of seen characters and their swapcases. If all characters have their counterparts, then the window is nice.
This JavaScript iteration considers every starting point in s. It builds sets of lowercase and uppercase characters and monitors the length of the sets. When they match, a nice substring is found, and it updates the result if longer than any previously found nice string.
JavaScript
C#
Time Complexity: O(n^2), where n is the number of characters.
Space Complexity: O(1), due to constant space used by sets independent of n.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Recursive Approach - Divide and Conquer | Time Complexity: O(n^2 * 2^n) in the worst case due to recursive checks at each point. |
| Sliding Window Approach | Time Complexity: O(n^2), where n is the number of characters. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Divide and Conquer | O(n^2) | O(n) | Best when explaining logic in interviews. Directly follows the definition of a nice substring and easy to reason about. |
| Sliding Window with Case Tracking | O(26 * n) ≈ O(n) | O(1) | Preferred when optimizing substring searches. Efficient for large inputs and demonstrates strong sliding window skills. |
LeetCode 1763. Longest Nice Substring | BiWeekly Contest 46| C++ | Algorithm Explained • Cherry Coding [IIT-G] • 11,138 views views
Watch 9 more video solutions →Practice Longest Nice Substring with our built-in code editor and test cases.
Practice on FleetCode