Abstract / Summary

Find the longest substring where every pair of adjacent characters occurs at most twice in the substring.

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

Typical patterns to solve this problem:

• 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 longestSemiRepetitiveSubstring method computes the length of the longest contiguous substring that contains at most one pair of adjacent equal characters. It processes the input string s with a two-pointer sliding window, expanding the right boundary while tracking the number of adjacent equal pairs (semi). When the count exceeds the allowed limit, the left boundary is moved forward until the window becomes valid again. The maximum valid window size encountered during the scan is stored in result and returned.

Key Steps

The algorithm begins by establishing the initial state of the sliding window.

result = 1
left = 0
semi = 0

result holds the best length found so far, left marks the start of the current window, and semi counts the adjacent equal pairs inside the window.

The main loop iterates the right pointer from the second character to the end of the string.

for right in range(1, len(s)):

Inside the loop the code checks whether the newly included character forms an adjacent pair with its predecessor.

if s[right] == s[right - 1]:
    semi += 1

If the window still satisfies the “at most one pair” condition, the length of the current window (right - left + 1) is compared with result and the larger value is kept.

if semi <= 1:
    result = max(result, right - left + 1)

When the count of adjacent pairs exceeds one, the algorithm contracts the window from the left until the excess pair is removed. The contraction proceeds one step at a time, and each step checks whether the step eliminates an adjacent pair.

else:
    while True:
        left += 1
        if s[left] == s[left - 1]:
            semi -= 1
            break

After the window has been restored to a valid state, the outer loop continues with the next right position. When the scan finishes, result contains the length of the longest semi-repetitive substring.

Edge Cases Handled

The implementation gracefully handles a string consisting of a single character. The initial result value of 1 correctly represents the only possible substring length, and the loop body is never entered because range(1, len(s)) is empty.

When the entire string is composed of the same character, each new character creates an adjacent pair, causing semi to increase rapidly. The inner while loop removes the leftmost character each time the count exceeds one, ensuring that the window never contains more than a single pair. Consequently, the algorithm returns 2, which is the longest substring allowed under the constraint.

If the input contains no adjacent equal characters, semi remains zero throughout the scan. The condition semi <= 1 is always true, and result expands to the full length of the string, delivering the correct maximal value.

The code also correctly processes strings where the only allowed pair appears at the very beginning or at the very end. The left pointer moves only when necessary, preserving the maximal window that includes the solitary pair.

Performance Optimizations

The sliding-window technique ensures that each character is examined a constant number of times: once when the right pointer includes it and at most once when the left pointer excludes it. This yields linear traversal without redundant rescanning of previously processed sections.

The use of a simple integer counter (semi) to track the number of adjacent equal pairs avoids the need for auxiliary data structures such as hash maps or frequency arrays. Updating this counter is an O(1) operation performed only when a pair is created or removed.

The inner while loop terminates as soon as the excess pair is eliminated, rather than iterating until the window size shrinks arbitrarily. This early exit prevents unnecessary pointer movements and keeps the overall work proportional to the length of the input.

All variables are scalar and the algorithm operates in constant extra space, independent of the input size. The combination of a single forward pass and minimal state updates makes the solution both time-efficient and memory-light.

Imagine you have a long row of colorful blocks with letters written on them. You want to pick a line of these blocks that stay right next to each other. The rule for your game is that you can have one spot where two identical blocks are touching, but you cannot have two spots like that.

The code starts by looking at the very first block and deciding it is the best one so far. It then starts walking down the line of blocks from left to right, one step at a time. Every time it finds two blocks next to each other that are the same, it marks that as a special pair.

If it finds that there is only one special pair, it measures how long the line of blocks is and remembers that length if it is the longest one seen yet. If it finds more than one special pair, the row has broken the rule. To fix this, it starts moving a helper along from the left side. This helper keeps moving forward and removing blocks until one of the special pairs disappears. Once that pair is gone and the rule is followed again, the code continues looking for even longer lines of blocks as it keeps walking toward the end of the row.

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	Java			C++		Python	TS
	WalkCCC	Java			C++		Python
	leetcode.ca	Java			C++	Go	Python	TS
	Progiez	Java			C++		Python
github	charles-wangkai	Java
	everthis			JS
	fsq		Rust
	varunu28	Java
	wisdompeak				C++
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
fsq	Rust
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