# Find the Longest Semi-Repetitive Substring
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-longest-semi-repetitive-substring)
Canonical: https://scaleengineer.com/dsa/problems/find-the-longest-semi-repetitive-substring
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** String
---
## Problem
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'`

# Approaches
## Brute Force Enumeration
The most straightforward approach is to generate every possible substring of the input string `s`, check each one to see if it's semi-repetitive, and keep track of the longest valid one found.
**Time:** O(n^3), where n is the length of the string `s`. Generating all substrings takes O(n^2) iterations. For each substring, checking if it's semi-repetitive takes up to O(n) time. This leads to a cubic time complexity. · **Space:** O(n) in the worst case, due to the space required to store the substring being checked. `s.substring()` can create a new string of length up to n.
**Pros:** Very simple to conceptualize and implement.; Guaranteed to be correct.
**Cons:** Highly inefficient due to its O(n^3) time complexity.; Not suitable for larger input sizes (though it passes for n <= 50).
### Explanation
This method systematically checks all substrings. A substring is defined by its start and end indices. We can use two nested loops to iterate through all possible start and end points. For each generated substring, a helper function is called to determine if it's semi-repetitive.

A string is semi-repetitive if it contains at most one pair of adjacent identical digits. The helper function `isSemiRepetitive` iterates through the substring and counts these pairs. If the count exceeds one, the substring is invalid. Otherwise, it's valid, and we compare its length with our current maximum.

```java
class Solution {
    private boolean isSemiRepetitive(String s) {
        int pairs = 0;
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                pairs++;
            }
        }
        return pairs <= 1;
    }

    public int longestSemiRepetitiveSubstring(String s) {
        int n = s.length();
        int maxLength = 0;
        if (n > 0) {
            maxLength = 1;
        }
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                String sub = s.substring(i, j + 1);
                if (isSemiRepetitive(sub)) {
                    maxLength = Math.max(maxLength, sub.length());
                }
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength` to 0.
- Use two nested loops with indices `i` and `j` to generate all substrings.
- For each substring, create a helper function `isSemiRepetitive` to check its validity.
- Inside the helper function, count the number of adjacent identical characters.
- If the count is at most 1, the substring is valid.
- If valid, update `maxLength` with the current substring's length if it's greater.
- Return `maxLength` after checking all substrings.

## Optimized Brute Force
This approach improves on the naive brute-force method by optimizing the check for the semi-repetitive property. Instead of re-evaluating each substring from scratch, we extend a substring one character at a time and maintain a running count of adjacent pairs.
**Time:** O(n^2). We have two nested loops, and the work inside the inner loop is constant time. · **Space:** O(1), as we only use a few variables to store the state (`maxLength`, `adjacentPairs`, loop indices).
**Pros:** A significant improvement over the O(n^3) approach.; Still relatively easy to understand.
**Cons:** Not the most optimal solution; can be improved to linear time.
### Explanation
We still use two nested loops to define our substrings. The outer loop fixes the starting point `i`, and the inner loop extends the substring by moving the endpoint `j`. For a fixed `i`, as we increment `j`, we only need to check the newly added character `s[j]` against its predecessor `s[j-1]`.

We keep a count of adjacent pairs for the current substring `s[i...j]`. If this count ever exceeds 1, we know that this substring and any longer one starting at `i` will also be invalid. This allows us to break the inner loop early and move to the next starting position `i`, avoiding unnecessary computations.

```java
class Solution {
    public int longestSemiRepetitiveSubstring(String s) {
        int n = s.length();
        if (n <= 1) {
            return n;
        }
        int maxLength = 1;
        for (int i = 0; i < n; i++) {
            int adjacentPairs = 0;
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(j) == s.charAt(j - 1)) {
                    adjacentPairs++;
                }
                if (adjacentPairs <= 1) {
                    maxLength = Math.max(maxLength, j - i + 1);
                } else {
                    break;
                }
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength` to 1.
- Use an outer loop `i` to iterate through all possible start indices.
- For each `i`, initialize `adjacentPairs = 0`.
- Use an inner loop `j` to extend the substring from `i`.
- As `j` increases, update `adjacentPairs` if `s[j] == s[j-1]`.
- If `adjacentPairs` becomes greater than 1, break the inner loop.
- Otherwise, update `maxLength` with the current valid substring's length.
- Return `maxLength`.

## Sliding Window
The most efficient solution utilizes the sliding window pattern. We maintain a 'window' (a substring) that is always semi-repetitive. We expand the window by moving its right boundary. If the window becomes invalid (more than one pair), we shrink it from the left until it's valid again, ensuring we only traverse the string once.
**Time:** O(n). Both the `left` and `right` pointers traverse the string at most once, resulting in a linear time complexity. · **Space:** O(1). We only use a few variables to keep track of pointers and the maximum length, regardless of the input size.
**Pros:** Optimal time complexity.; Efficient for any input size.
**Cons:** The logic can be slightly more complex to devise compared to brute-force methods.
### Explanation
This approach uses two pointers, `left` and `right`, to define the current window `s[left...right]`. The `right` pointer always moves forward to expand the window. The `left` pointer only moves forward when the window needs to be shrunk.

To efficiently track the validity of the window, we only need to remember the position of the *first* adjacent pair we encounter. Let's say we store the index of the second character of this pair in `lastPairIndex`. When we find a new pair at `right`, if `lastPairIndex` is already set, it means we've found a second pair. To make the window valid again, we must slide the `left` pointer to the position of that first pair. We then update `lastPairIndex` to the position of the new pair. At each step, we calculate the length of the current valid window and update our overall maximum length.

```java
class Solution {
    public int longestSemiRepetitiveSubstring(String s) {
        int n = s.length();
        if (n <= 2) {
            return n;
        }
        int maxLength = 1;
        int left = 0;
        // Stores the index of the second character of the first pair in the current window
        int lastPairIndex = -1; 

        for (int right = 1; right < n; right++) {
            if (s.charAt(right) == s.charAt(right - 1)) {
                if (lastPairIndex != -1) {
                    // This is the second pair, shrink the window
                    left = lastPairIndex;
                }
                // Record the position of the current pair
                lastPairIndex = right;
            }
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize pointers `left = 0`, `right = 0`, and a variable `lastPairIndex = -1`.
- Iterate `right` from 1 to `n-1`.
- If `s[right] == s[right-1]`, a pair is found.
- If this is the second pair in the window (i.e., `lastPairIndex != -1`), shrink the window by setting `left = lastPairIndex`.
- Update `lastPairIndex` to the current pair's position (`right`).
- In each iteration, update `maxLength` with the size of the current valid window (`right - left + 1`).
- Return `maxLength`.

# Solutions
### Java

```java
class Solution {
public
  int longestSemiRepetitiveSubstring(String s) {
    int n = s.length();
    int ans = 0;
    for (int i = 0, j = 0, cnt = 0; i < n; ++i) {
      if (i > 0 && s.charAt(i) == s.charAt(i - 1)) {
        ++cnt;
      }
      while (cnt > 1) {
        if (s.charAt(j) == s.charAt(j + 1)) {
          --cnt;
        }
        ++j;
      }
      ans = Math.max(ans, i - j + 1);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int longestSemiRepetitiveSubstring(string s) {
    int n = s.size();
    int ans = 0;
    for (int i = 0, j = 0, cnt = 0; i < n; ++i) {
      if (i && s[i] == s[i - 1]) {
        ++cnt;
      }
      while (cnt > 1) {
        if (s[j] == s[j + 1]) {
          --cnt;
        }
        ++j;
      }
      ans = max(ans, i - j + 1);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def longestSemiRepetitiveSubstring(self, s: str) -> int: n = len(s) ans = cnt = j = 0 for i in range(n): if i and s[i] == s[i - 1]: cnt += 1 while cnt > 1: if s[j] == s[j + 1]: cnt -= 1 j += 1 ans = max(ans, i - j + 1) return ans

```