Find the Longest Semi-Repetitive Substring

Medium
1247.

Find the Longest Semi-Repetitive Substring

Find the Longest Semi-Repetitive Substring is a medium coding problem on strings and sliding window, asked in Amazon and Google interviews.

You are given a string s of digits. A string is semi-repetitive if it contains at most one pair of adjacent equal characters. For example "0010", "2026" and "54944" are semi-repetitive, while "00101022" (two pairs) and "1101234883" (two pairs) are not.

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

Example 1

Input
s = "11233"
Output
4
Explanation
The whole string has two adjacent pairs (`11` and `33`); `"1123"` and `"1233"` keep just one.

Example 2

Input
s = "2026"
Output
4
Explanation
No adjacent pair at all.

Example 3

Input
s = "1111"
Output
2

Constraints

  • 1 <= s.length <= 50
  • '0' <= s[i] <= '9'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var longestSemiRepetitiveSubstring = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find the Longest Semi-Repetitive Substring — Solution

Find the Longest Semi-Repetitive Substring solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Find the Longest Semi-Repetitive Substring is a medium coding problem on strings and sliding window, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Strings, Sliding Window
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a string s of digits. A string is semi-repetitive if it contains at most one pair of adjacent equal characters. For example "0010", "2026" and "54944" are semi-repetitive, while "00101022" (two pairs) and "1101234883" (two pairs) are not.

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

Example 1

Input: s = "11233"
Output: 4
Explanation: The whole string has two adjacent pairs (`11` and `33`); `"1123"` and `"1233"` keep just one.

Example 2

Input: s = "2026"
Output: 4
Explanation: No adjacent pair at all.

Example 3

Input: s = "1111"
Output: 2

Constraints

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

Hints for Find the Longest Semi-Repetitive Substring

  1. Hint 1

    Think of a window [l, r] and the number of positions i in it with s[i] == s[i + 1].

  2. Hint 2

    Growing the window to the right can add a pair; shrinking from the left can remove one.

  3. Hint 3

    Sliding window: extend r, and while the window holds two pairs, advance l (dropping the pair at l when s[l] == s[l + 1]). Track the longest window.

How to solve Find the Longest Semi-Repetitive Substring

A sliding window that keeps at most one adjacent equal pair inside; the longest window seen is the answer.

Approach

  1. Set l = 0, pairs = 0, best = 1.
  2. For each r from 1 to n - 1: if s[r] == s[r - 1], increase pairs.
  3. While pairs > 1: if s[l] == s[l + 1], decrease pairs; then increase l.
  4. Update best = max(best, r - l + 1).

Why it works

pairs always counts the adjacent equal pairs fully inside [l, r]: a new pair enters when r advances onto a repeat, and the pair (l, l + 1) leaves when l advances past it. For each r, the loop moves l to the smallest index that keeps the window valid, so [l, r] is the longest semi-repetitive substring ending at r; validity is monotone (shrinking never adds pairs), which makes the two-pointer sweep correct.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • A string of length 1 is semi-repetitive; start best at 1.
  • When shrinking, check the pair (l, l + 1) before moving l.
  • Pairs may overlap: "111" already holds two of them, so it is not semi-repetitive.

Reference solution

Python

def longestSemiRepetitiveSubstring(s: str) -> int:
    l = 0
    pairs = 0
    best = 1
    for r in range(1, len(s)):
        if s[r] == s[r - 1]:
            pairs += 1
        while pairs > 1:
            if s[l] == s[l + 1]:
                pairs -= 1
            l += 1
        best = max(best, r - l + 1)
    return best

Java

public static int longestSemiRepetitiveSubstring(String s) {
    int l = 0, pairs = 0, best = 1;
    for (int r = 1; r < s.length(); r++) {
        if (s.charAt(r) == s.charAt(r - 1)) pairs++;
        while (pairs > 1) {
            if (s.charAt(l) == s.charAt(l + 1)) pairs--;
            l++;
        }
        best = Math.max(best, r - l + 1);
    }
    return best;
}

C++

int longestSemiRepetitiveSubstring(string s) {
    int l = 0, pairs = 0, best = 1;
    for (int r = 1; r < (int)s.size(); r++) {
        if (s[r] == s[r - 1]) pairs++;
        while (pairs > 1) {
            if (s[l] == s[l + 1]) pairs--;
            l++;
        }
        best = max(best, r - l + 1);
    }
    return best;
}

JavaScript

var longestSemiRepetitiveSubstring = function(s) {
    var l = 0, pairs = 0, best = 1;
    for (var r = 1; r < s.length; r++) {
        if (s[r] === s[r - 1]) pairs++;
        while (pairs > 1) {
            if (s[l] === s[l + 1]) pairs--;
            l++;
        }
        best = Math.max(best, r - l + 1);
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Sliding Window Technique