Find the Longest Semi-Repetitive Substring

medium string sliding window two pointers

Problem

You are given a string s made up of digits. A string is called semi-repetitive if it contains at most one place where two side-by-side characters are equal (in other words, at most one adjacent equal pair). Return the length of the longest contiguous substring of s that is semi-repetitive.

Inputs = "52233"

Output4

The whole string has two adjacent equal pairs: "22" and "33". The substring "5223" (indices 0..3) has only the pair "22", so it is semi-repetitive and has length 4. No semi-repetitive substring is longer.

s (digits)

def longest_semi_repetitive_substring(s):
    left = 0
    pairs = 0
    best = 1
    for right in range(1, len(s)):
        if s[right] == s[right - 1]:
            pairs += 1
        while pairs > 1:
            if s[left] == s[left + 1]:
                pairs -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

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

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

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

Explanation

The only thing that makes a string not semi-repetitive is having two or more spots where two neighbours are equal. So instead of checking every substring, we slide a window across the string and keep track of how many such adjacent equal pairs currently sit inside the window.

We use two pointers, left and right. As right moves forward one character at a time, we check the pair (s[right-1], s[right]). If those two characters are equal, the window just gained one more adjacent pair, so we bump the pairs counter.

The window is allowed to hold at most one such pair. The moment pairs climbs to 2, the window is no longer valid, so we slide left forward. Each time the character leaving the window was itself the start of an adjacent pair, that pair is gone, so we drop pairs back down. We keep shrinking until pairs is back to one.

After every move of right, the window from left to right is the longest valid window ending at right, so we record its length right − left + 1 in best.

Tracing s = "52233": the window grows to "522" (one pair "22"), then to "5223" (still one pair, length 4 — our best). Adding the final "3" creates the pair "33", giving two pairs, so left slides past the "22" until only "33" remains. The longest semi-repetitive window stays at length 4.

Time: O(n) Space: O(1)