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.

Description Hints 1 Solution Video 11:36

1763. Longest Nice Substring

Easy65.0% acceptance4 companies

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.

Asked at 4 companies

Microsoft

Google Amazon Bloomberg

Topics

Hints open one at a time

Hint 1

Brute force and check each substring to see if it is nice.

11:36

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution