DSA problem
Longest Nice Substring
A string s is nice if for every letter that appears in it, both the uppercase and the lowercase forms also appear in it. For example, "abABB" is nice because both 'A' and 'a' appear, and both 'B' and 'b' appear; "abA" is not nice because 'b' appears but 'B' does not. Given a string s, return the longest substring of s that is nice. If there are multiple substrings of equal greatest length, return the one that occurs the earliest. If no nice substring exists, return an empty string.
The brute-force approach enumerates every substring and checks the nice property, costing O(n^3) or O(n^2) with careful bookkeeping. We can do dramatically better by recognising a clean recursive structure: if a character c appears in the string but its case partner does not, then c can never be part of any nice substring. That means every nice substring must lie entirely on one side of c — it cannot straddle that character. This observation turns the problem into a divide-and-conquer recursion.
The algorithm: scan the string once to collect the set of characters present. If every character also has its case partner present, the entire string is itself nice — return it. Otherwise, find the first character whose partner is absent; this character is a "splitter". Split the string on every occurrence of the splitter into segments, recursively solve each segment, and return the longest result, preferring the earliest in case of ties.
Each level of recursion does O(n) work and reduces the alphabet of every segment by at least one distinct letter (the splitter is gone for good). Since the alphabet has only 52 letters, the recursion depth is bounded by 52, giving an overall complexity of O(n · 52) = O(n) ignoring constant factors, with O(n) auxiliary space for the recursion stack and substring slices. The recursion is the natural divide-and-conquer pattern: divide the input on a disqualifying character, conquer each subproblem, and combine by taking the longest answer.
Examples
s = "YazaAay""aAa"s = "Bb""Bb"s = "c"""Constraints
- 1 <= s.length <= 100
- s consists of uppercase and lowercase English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.