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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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

1
2
3
4
5
6
7
8


Input: s = "5494"

Output: 4

Explanation:

`s` is a semi-repetitive string.

Example 3

1
2
3
4
5
6
7
8
9


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'

Solution

Method 1 – Sliding Window

Intuition

We want the longest substring with at most one pair of adjacent equal digits. We can use a sliding window to keep track of the current substring and count the number of adjacent equal pairs.

Approach

  1. Initialize two pointers (left and right) for the window and a counter for adjacent equal pairs.
  2. Move the right pointer through the string:
    • If s[right] == s[right-1], increment the counter.
    • If the counter exceeds 1, move the left pointer forward and decrement the counter when needed.
  3. Track the maximum window length where the counter is at most 1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int longestSemiRepetitiveSubstring(string s) {
        int n = s.size(), ans = 1, cnt = 0, l = 0;
        for(int r = 1; r < n; ++r) {
            if(s[r] == s[r-1]) ++cnt;
            while(cnt > 1) {
                if(s[l+1] == s[l]) --cnt;
                ++l;
            }
            ans = max(ans, r-l+1);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func longestSemiRepetitiveSubstring(s string) int {
    n, ans, cnt, l := len(s), 1, 0, 0
    for r := 1; r < n; r++ {
        if s[r] == s[r-1] { cnt++ }
        for cnt > 1 {
            if s[l+1] == s[l] { cnt-- }
            l++
        }
        if r-l+1 > ans { ans = r-l+1 }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int longestSemiRepetitiveSubstring(String s) {
        int n = s.length(), ans = 1, cnt = 0, l = 0;
        for(int r = 1; r < n; ++r) {
            if(s.charAt(r) == s.charAt(r-1)) ++cnt;
            while(cnt > 1) {
                if(s.charAt(l+1) == s.charAt(l)) --cnt;
                ++l;
            }
            ans = Math.max(ans, r-l+1);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun longestSemiRepetitiveSubstring(s: String): Int {
        var ans = 1; var cnt = 0; var l = 0
        for (r in 1 until s.length) {
            if (s[r] == s[r-1]) cnt++
            while (cnt > 1) {
                if (s[l+1] == s[l]) cnt--
                l++
            }
            ans = maxOf(ans, r-l+1)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def longestSemiRepetitiveSubstring(self, s: str) -> int:
        n = len(s)
        ans = 1
        cnt = 0
        l = 0
        for r in range(1, n):
            if s[r] == s[r-1]:
                cnt += 1
            while cnt > 1:
                if s[l+1] == s[l]:
                    cnt -= 1
                l += 1
            ans = max(ans, r-l+1)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn longest_semi_repetitive_substring(s: String) -> i32 {
        let s = s.as_bytes();
        let n = s.len();
        let (mut ans, mut cnt, mut l) = (1, 0, 0);
        for r in 1..n {
            if s[r] == s[r-1] { cnt += 1; }
            while cnt > 1 {
                if s[l+1] == s[l] { cnt -= 1; }
                l += 1;
            }
            ans = ans.max(r-l+1);
        }
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    longestSemiRepetitiveSubstring(s: string): number {
        let n = s.length, ans = 1, cnt = 0, l = 0;
        for(let r=1;r<n;++r) {
            if(s[r]===s[r-1]) ++cnt;
            while(cnt>1) {
                if(s[l+1]===s[l]) --cnt;
                ++l;
            }
            ans = Math.max(ans, r-l+1);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), since each character is visited at most twice.
  • 🧺 Space complexity: O(1), only a few variables are used.