Skip to main content
Talentd

Longest Nice Substring - Solution & Explanation

EasyHash TableStringDivide and ConquerBit Manipulation8 min readAsked at: Amazon, Microsoft, Google +1
Practice this problem

Problem Statement

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 <= 100
  • s consists of uppercase and lowercase English letters.

Approach Overview

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.

Approach 1: Recursive Approach - Divide and Conquer

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor →

Approach 2: Sliding Window Approach

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.

Code

JavaScriptC#

JavaScript

C#

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive Approach - Divide and Conquer

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.

Sliding Window Approach

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.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive Divide and ConquerO(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 TrackingO(26 * n) ≈ O(n)O(1)Preferred when optimizing substring searches. Efficient for large inputs and demonstrates strong sliding window skills.

Video Solution

LeetCode 1763. Longest Nice Substring | BiWeekly Contest 46| C++ | Algorithm Explained • Cherry Coding [IIT-G] • 11,521 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Longest Nice Substring easy or hard?
The problem is labeled Easy on LeetCode, mainly because the divide-and-conquer idea is straightforward once you notice that invalid characters can split the string. However, designing the optimal sliding window version requires stronger string manipulation and window management skills.
Longest Nice Substring Python/Java solution
Python and Java implementations often use a recursive divide-and-conquer strategy. The algorithm builds a set of characters in the current substring, finds characters missing their opposite case, splits around them, and returns the longest valid result from the recursive calls.
How to solve Longest Nice Substring in O(n)?
Use a sliding window approach combined with character frequency tracking. Iterate over possible counts of unique characters (1–26) and maintain two pointers to expand or shrink the window while tracking uppercase and lowercase occurrences. Each character is processed a constant number of times, resulting in roughly O(n) time complexity.
What is the best approach for Longest Nice Substring?
The divide and conquer approach is the most commonly used solution. It scans the string to find characters that do not have their opposite case and splits the string around them, recursively solving smaller substrings. This method clearly follows the problem definition and typically runs in O(n^2) time in the worst case.
Is Longest Nice Substring asked at Google/Amazon/Meta?
Problems involving substring validation, case tracking, and divide-and-conquer patterns are common in interviews at companies like Amazon and Google. While this exact problem may vary, the techniques—sliding window, set lookups, and recursive partitioning—appear frequently in string interview questions.
What data structure is used in Longest Nice Substring?
Typical implementations use a hash set or hash map to track characters in the current substring. Some optimized solutions also use bit masks or fixed arrays to track uppercase and lowercase letters efficiently.
What is the time complexity of Longest Nice Substring?
The recursive divide-and-conquer solution has O(n^2) worst-case time complexity because multiple substrings may be evaluated. A sliding window optimization can reduce the effective runtime to about O(26 * n), which simplifies to O(n) since the alphabet size is constant.

Ready to solve this problem?

Practice Longest Nice Substring with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of Good Paths