Longest Nice Substring - Video Solutions

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.