Skip to content

2730. Find the Longest Semi-Repetitive Substring

Description

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'

Solutions

Solution 1: Two Pointers

Thinking

A semi-repetitive string has at most one pair of equal adjacent characters; we want its maximum length. Checking every pair of endpoints is impossible at \(n\le 10^5\).

Move the right end and count equal adjacent pairs. When the count exceeds \(1\), advance the left end until the window is legal. The longest such window is the answer.

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)\).

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int longestSemiRepetitiveSubstring(String s) {
        int ans = 1, n = s.length();
        for (int i = 1, j = 0, cnt = 0; i < n; ++i) {
            cnt += s.charAt(i) == s.charAt(i - 1) ? 1 : 0;
            for (; cnt > 1; ++j) {
                cnt -= s.charAt(j) == s.charAt(j + 1) ? 1 : 0;
            }
            ans = Math.max(ans, i - j + 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 ans = 1, n = s.size();
        for (int i = 1, j = 0, cnt = 0; i < n; ++i) {
            cnt += s[i] == s[i - 1] ? 1 : 0;
            for (; cnt > 1; ++j) {
                cnt -= s[j] == s[j + 1] ? 1 : 0;
            }
            ans = max(ans, i - j + 1);
        }
        return ans;
    }
};

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function longestSemiRepetitiveSubstring(s: string): number {
    const n = s.length;
    let ans = 1;
    for (let i = 1, j = 0, cnt = 0; i < n; ++i) {
        cnt += s[i] === s[i - 1] ? 1 : 0;
        for (; cnt > 1; ++j) {
            cnt -= s[j] === s[j + 1] ? 1 : 0;
        }
        ans = Math.max(ans, i - j + 1);
    }
    return ans;
}

Solution 2: Two Pointers (Optimization)

Thinking

Solution 1 may shrink many times and track a running maximum. Only the length is required, so each violation moves the left end once. The window never shrinks, and \(n-l\) is the longest legal length.

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)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def longestSemiRepetitiveSubstring(self, s: str) -> int:
        n = len(s)
        cnt = l = 0
        for i in range(1, n):
            cnt += s[i] == s[i - 1]
            if cnt > 1:
                cnt -= s[l] == s[l + 1]
                l += 1
        return n - l

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

 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();
        int cnt = 0, l = 0;
        for (int i = 1; i < n; ++i) {
            cnt += s[i] == s[i - 1] ? 1 : 0;
            if (cnt > 1) {
                cnt -= s[l] == s[++l] ? 1 : 0;
            }
        }
        return n - l;
    }
};

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function longestSemiRepetitiveSubstring(s: string): number {
    const n = s.length;
    let [cnt, l] = [0, 0];
    for (let i = 1; i < n; ++i) {
        cnt += s[i] === s[i - 1] ? 1 : 0;
        if (cnt > 1) {
            cnt -= s[l] === s[l + 1] ? 1 : 0;
            ++l;
        }
    }
    return n - l;
}

Comments