Abstract / Summary

Check if some substring of a string also appears in the reverse of that string.

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% (70k+ submissions).

Typical patterns to solve this problem:

• Hash Table
• 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 Solution.isSubstringPresent method determines whether a given lowercase alphabetic string contains any length-two substring that appears at least twice, either as an identical pair or as the reverse of a previously seen pair. The implementation relies on a compact representation of all possible two-character combinations and performs a single forward scan with an optional early return, followed by a second scan that checks for reversed pairs.

Core Components

The method defines a small helper to map a pair of characters to a unique index in a fixed-size boolean array.

def hash(a, b):
    return (ord(a) - 97) * 26 + ord(b) - 97

The array have holds a flag for each of the 26 × 26 possible ordered pairs.

have = [False] * (26 * 26)

First Pass - Recording and Immediate Detection

During the first traversal of adjacent character pairs, each pair is recorded in have. The loop also checks two conditions that allow an immediate True result:

1. The current pair consists of identical characters (a == b).
2. The reverse of the current pair has already been recorded (have[hash(b, a)]).

for a, b in zip(s, s[1:]):
    have[hash(a, b)] = True
    if a == b or have[hash(b, a)]:  # early exit
        return True

If either condition is satisfied, the method returns early, avoiding further work.

Second Pass - Detecting Reversed Pairs

If the first pass completes without triggering the early exit, a second scan looks specifically for any pair whose reverse was seen earlier. Because the forward pass already marked all pairs, this loop simply queries the have array for the reversed index.

for a, b in zip(s, s[1:]):
    if have[hash(b, a)]:
        return True

If a reversed pair is found, the method returns True; otherwise it falls through to the final False.

return False

Edge Cases Handled

The algorithm gracefully handles strings of length zero or one. In those cases, the zip(s, s[1:]) iterator yields no elements, so both loops are skipped and the method returns False, correctly indicating that no length-two substring can exist.

When the input contains consecutive identical characters (e.g., "aa"), the condition a == b triggers the early exit, returning True without further processing.

Strings that contain a pair and later its reverse (e.g., "ab...ba") are detected either during the first pass-if the reverse appears after the original pair-or during the second pass, ensuring that non-adjacent reversed occurrences are also recognized.

Performance Optimizations

The implementation achieves high efficiency through several deliberate choices:

• Fixed-size Boolean Array: By allocating a list of 676 booleans (26 * 26), the code avoids dynamic data structures such as dictionaries or sets. Index calculation via the hash function is a constant-time arithmetic operation, providing O(1) access for both marking and lookup.

• Early Exit Strategy: The first loop incorporates a combined check for identical characters and previously seen reversed pairs. When either condition holds, the function returns immediately, preventing unnecessary iteration over the remainder of the string.

• Two-Pass Design with Minimal Overhead: The second pass reuses the same have array without additional allocations. Because the first pass already populated the array, the second pass consists solely of hash computation and a boolean check, both of which are inexpensive.

• Linear Traversal of Adjacent Pairs: Both loops iterate over zip(s, s[1:]), which yields each adjacent character pair exactly once. This ensures that the total work scales linearly with the length of the input string, while the constant-time operations inside the loops keep the per-iteration cost low.

Overall, the method combines a compact representation of the problem space with early termination logic to deliver a fast solution for detecting repeated or reversed length-two substrings in a lowercase alphabetic string.

Imagine a long snake made of colored blocks, and each block has a letter on it. The job is to see if any pair of blocks next to each other appears again in the snake, but flipped around like a mirror image.

First, there is a tiny machine that gives every possible pair of letters a special number. If the blocks are a and b, the machine does some math to turn that pair into a spot on a checklist.

The code walks along the snake from the beginning to the end. It looks at every two neighbors, finds their special number, and marks that spot on the checklist as found. While doing this, it watches closely to see if it just found a pair that matches its own reflection, or a pair that looks exactly like one it already saw flipped around. If it sees that, the work is done right away.

If it finishes walking and has not found any twins yet, it walks along the snake one more time. This second walk checks the original list against the flipped versions to make sure nothing was missed. If anything matches, the answer is found.

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

Time: linear
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			Python	Java	C++		TS
	WalkCCC			Python	Java	C++
	leetcode.ca			Python	Java	C++	Go	TS
	Progiez			Python	Java	C++
github	charles-wangkai				Java
	everthis	JS
	fartem		Ruby
	fsq					C++
	JoshCrozier	JS
	trung-hn			Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
trung-hn	Python

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