Skip to main content
Talentd

Find the Longest Semi-Repetitive Substring - Solution & Explanation

MediumStringSliding Window13 min read
Practice this problem

Problem Statement

You are given a digit string s that consists of digits from 0 to 9.

A string is called semi-repetitive if there is at most one adjacent pair of the same digit. For example, "0010", "002020", "0123", "2002", and "54944" are semi-repetitive while the following are not: "00101022" (adjacent same digit pairs are 00 and 22), and "1101234883" (adjacent same digit pairs are 11 and 88).

Return the length of the longest semi-repetitive substring of s.

 

Example 1:

Input: s = "52233"

Output: 4

Explanation:

The longest semi-repetitive substring is "5223". Picking the whole string "52233" has two adjacent same digit pairs 22 and 33, but at most one is allowed.

Example 2:

Input: s = "5494"

Output: 4

Explanation:

s is a semi-repetitive string.

Example 3:

Input: s = "1111111"

Output: 2

Explanation:

The longest semi-repetitive substring is "11". Picking the substring "111" has two adjacent same digit pairs, but at most one is allowed.

 

Constraints:

  • 1 <= s.length <= 50
  • '0' <= s[i] <= '9'

Approach Overview

Problem Overview: Given a numeric string s, return the length of the longest substring that is semi-repetitive. A substring is semi-repetitive if it contains at most one pair of equal adjacent characters (for example "11"). The goal is to scan the string and keep the longest window where this condition holds.

Approach 1: Sliding Window (O(n) time, O(1) space)

This problem fits naturally into a sliding window pattern. Maintain two pointers left and right that represent the current substring window. While expanding the window to the right, count how many adjacent equal pairs appear (i.e., when s[i] == s[i-1]). If the count exceeds one, move the left pointer forward until the window again contains at most one such pair. Each character enters and leaves the window at most once, so the scan runs in O(n) time with constant extra memory. This approach is optimal and very common in substring problems involving constraints.

Approach 2: Dynamic Programming Tracking Adjacent Pairs (O(n) time, O(1) space)

A dynamic programming view keeps track of the most recent index where an adjacent duplicate occurred. While iterating through the string, store the index of the previous duplicate pair and the one before it. If a new pair appears, update the window start to the position after the earlier pair so that the substring still contains at most one duplicate pair. This effectively maintains the longest valid substring ending at each position. The algorithm still performs a single pass through the string, giving O(n) time and constant space. Some implementations describe this as DP because the current state depends on previously tracked pair positions.

Recommended for interviews: The sliding window solution is the approach most interviewers expect. It demonstrates strong control over substring constraints and two-pointer techniques. A brute-force enumeration of all substrings would show understanding but runs in O(n^2) or worse. The optimal sliding window solution proves you can maintain constraints efficiently while scanning the string once.

Approach 1: Sliding Window Approach

This approach employs a sliding window strategy to keep track of semi-repetitive substrings. The window will expand by moving the end pointer through the string. If the window contains more than one adjacent pair of the same digits, the start pointer will increment to maintain the semi-repetitive property. This method efficiently finds the longest valid substring in linear time.

The function uses a single loop to adjust the sliding window's end pointer. It keeps count of adjacent similar digit pairs and adjusts the start pointer as necessary to ensure that no more than one pair exists in the window. By doing this, the function dynamically assesses and updates the longest valid substring's length.

Code

PythonJavaScript

Python

JavaScript

Complexity

The algorithm runs in O(n) time complexity, where n is the length of the string, as each character is processed once. Its space complexity is O(1), as it uses a fixed amount of extra space.

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

The dynamic programming approach involves creating a table that stores the length of the longest semi-repetitive substring ending at each character. This table is updated incrementally by considering previous computations to find an optimal solution. The approach ensures that only allowable adjacent pairs are counted to maintain valid substrings.

The logic here is to update the length of the potential substring at each step, keeping the adjacent counter in check. Whenever more than one adjacent pair is detected, the dynamic calculation is reset, ensuring no invalid patterns extend beyond their limits.

Code

JavaC++

Java

C++

Complexity

The complexity here is also O(n) time due to a single traversal of the string. Space complexity remains O(1) as no additional data structures are used beyond primitive types.

Try this approach in the editor →

Approach 3: Two Pointers

We use two pointers to maintain a range s[j..i] such that there is at most one pair of adjacent characters that are equal, initially j = 0, i = 1. Initialize the answer ans = 1.

We use cnt to record the number of pairs of adjacent characters that are equal in the range. If cnt > 1, then we need to move the left pointer j until cnt \le 1. Each time, we update the answer as ans = max(ans, i - j + 1).

The time complexity is O(n), where n is the length of the string. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 4: Two Pointers (Optimization)

Since the problem only requires us to find the length of the longest semi-repetitive substring, each time the number of adjacent identical characters in the interval exceeds 1, we can move the left pointer l once, while the right pointer r continues to move to the right. This ensures that the length of the substring does not decrease.

Finally, the answer is n - l, where n is the length of the string.

The time complexity is O(n), where n is the length of the string. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sliding Window Approach

The algorithm runs in O(n) time complexity, where n is the length of the string, as each character is processed once. Its space complexity is O(1), as it uses a fixed amount of extra space.

Dynamic Programming Approach

The complexity here is also O(n) time due to a single traversal of the string. Space complexity remains O(1) as no additional data structures are used beyond primitive types.

Two Pointers—
Two Pointers (Optimization)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sliding WindowO(n)O(1)Best general solution for substring constraints with limited violations
Dynamic Programming (Track Duplicate Pair Positions)O(n)O(1)Useful when modeling the problem as state transitions while scanning the string

Video Solution

2730. Find the Longest Semi-Repetitive Substring | LEETCODE BIWEEKLY 106 • code Explainer • 911 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find the Longest Semi-Repetitive Substring easy or hard?
The problem is rated Medium because recognizing the sliding window constraint is the main challenge. Once you track adjacent duplicate pairs correctly, the implementation becomes straightforward and runs in linear time.
Find the Longest Semi-Repetitive Substring Python/Java solution
Python and Java implementations typically use the sliding window technique. Maintain two indices for the window and a counter for adjacent duplicate pairs. Java and C++ versions may also use a dynamic programming style approach that tracks the last two duplicate pair positions while iterating through the string.
How to solve Find the Longest Semi-Repetitive Substring in O(n)?
Use a sliding window with two pointers. Expand the right pointer across the string and count occurrences where s[i] equals s[i-1]. If more than one adjacent duplicate pair appears, move the left pointer forward until only one pair remains. Track the maximum window length during the scan to get the final answer.
What is the best approach for Find the Longest Semi-Repetitive Substring?
The sliding window approach is the most efficient and widely expected solution. Maintain a window with two pointers and track how many adjacent equal pairs exist inside it. If the count exceeds one, move the left pointer forward until the constraint is satisfied again. This method processes the string in O(n) time with O(1) space.
Is Find the Longest Semi-Repetitive Substring asked at Google/Amazon/Meta?
Problems involving sliding window substring constraints are common in interviews at companies like Google, Amazon, and Meta. While this exact problem may not always appear, the pattern of maintaining a window with limited violations is a frequent interview topic.
What data structure is used in Find the Longest Semi-Repetitive Substring?
The solution mainly relies on the sliding window technique with two pointers and simple counters. No complex data structures are required, though understanding string traversal and window maintenance is essential.
What is the time complexity of Find the Longest Semi-Repetitive Substring?
The optimal solution runs in O(n) time because the string is scanned once using a sliding window or a single-pass state tracking method. Each character is processed at most twice when the window expands and contracts. Space complexity is O(1) since only a few counters or indices are stored.

Ready to solve this problem?

Practice Find the Longest Semi-Repetitive Substring with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring