Abstract / Summary

Find the longest substring where for every letter there is another of the same letter.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 65% (100k+ submissions).

Typical patterns to solve this problem:

• Bit Manipulation
• Divide And Conquer
• Hash Table
• Sliding Window
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a method longestNiceSubstring that receives a string s and returns the longest substring in which every character appears together with its opposite case (lower-case paired with upper-case and vice-versa). The algorithm builds a mapping between each letter and its counterpart case, then examines all possible substrings in decreasing length order, updating the result when a “nice” substring is found.

Key Steps

The first important step creates a bi-directional lookup that converts any alphabetic character to its opposite case. This mapping is later used to verify the “nice” property of a candidate substring.

abc = "abcdefghijklmnopqrstuvwxyz"
lower2upper = {c: c.upper() for c in abc}
upper2lower = {c.upper(): c for c in abc}
flip = lower2upper | upper2lower

Next, the algorithm records the length of the input string and initializes an empty string to hold the best answer found so far.

size = len(s)
result = ""

The core of the solution consists of two nested loops that enumerate every possible substring. The outer loop selects a start index i. The inner loop chooses an end index j that runs from the full length of the string down to i + 1. By iterating j in reverse order, longer substrings are examined before shorter ones.

for i in range(size):
    for j in range(size, i, -1):

A short-circuit condition prevents unnecessary work when the remaining candidate length cannot exceed the length of the current best result. If the distance j - i is not greater than len(result), the inner loop breaks early, skipping all shorter substrings that start at the same i.

if j - i <= len(result):
    break

For each candidate substring, the slice operation extracts the characters between i (inclusive) and j (exclusive). The algorithm then checks whether every character in this slice has its opposite case present somewhere in the same slice. The all function together with a generator expression performs this verification. The expression flip[c] in set(current) builds a set of the characters in the current substring once per candidate, enabling constant-time membership tests for each character.

current = s[i:j]
if all(flip[c] in set(current) for c in current):
    result = current

When the condition holds, the current substring satisfies the “nice” definition and replaces the previous result because the loops guarantee that it is at least as long as any previously found nice substring.

Finally, after all start positions have been processed, the method returns the longest nice substring discovered, or an empty string if none exists.

return result

Edge Cases Handled

The algorithm naturally accommodates several edge conditions without additional code. When the input string is empty, size becomes zero, the outer loop does not execute, and the method returns the initially empty result. If the string contains only one character, the inner loop will generate a candidate of length one, but the “nice” check fails because the opposite case is missing, leaving result unchanged. Strings that consist entirely of characters lacking a counterpart case (for example, all lower-case letters) also result in an empty output because the verification step never succeeds.

Because the mapping flip includes entries for both lower-case and upper-case letters, the check works correctly regardless of the case distribution in the input. Non-alphabetic characters are not present in the mapping; however, the generator expression only accesses flip[c] for characters that appear in the substring. Since the problem domain restricts input to alphabetic characters, the code safely assumes that every character has a defined opposite case.

Performance Optimizations

A notable optimization is the early termination of the inner loop when the remaining substring length cannot improve the current best answer. By comparing j - i with len(result), the algorithm avoids generating and testing substrings that are guaranteed to be shorter than the best known nice substring, reducing the total number of iterations.

Another subtle optimization is the construction of a set from the current substring inside the all check. Converting the slice to a set once per candidate enables O(1) membership tests for each character, rather than scanning the substring repeatedly. This approach balances the overhead of set creation against the cost of repeated linear scans, yielding faster verification for longer substrings.

The use of the dictionary union operator (|) to merge the lower-to-upper and upper-to-lower maps creates a single lookup table in constant time, simplifying the case-flipping operation and avoiding conditional logic during the verification step.

Overall, the combination of reverse length iteration, early break based on current result length, and set-based membership testing constitutes the primary performance-focused design choices in the code.

Imagine there is a big collection of colorful letter blocks. Some are little lowercase letters and some are big uppercase ones. A word is considered nice if every letter inside it has both its little version and its big version present nearby.

The code starts by looking at every possible small piece of a word one by one. It picks a starting point and an ending point to carve out a slice of the letters. After cutting out a slice, it checks the contents carefully. It looks at every single letter in that slice and makes sure that its partner exists in the same group. For example, if there is a little a, there must be a big A in that same piece. If it finds a piece where every letter has its partner, it remembers that slice as the best one found so far. It keeps trying different slices to see if it can find a longer one that still follows these rules. By the time it finishes checking every combination, it has discovered the longest nice word hidden inside the collection.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java			TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java	Go		TS
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fsq	C++
	halfrost					Go
	haoel	C++
	JoshCrozier			JS
	lkwq007		Python
	suxrobGM						C#
	trung-hn		Python
	varunu28				Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
trung-hn	Python
varunu28	Java
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality