Introduction

In this blog post, we will explore how to solve the LeetCode problem "2730" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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'

Explanation

• Sliding Window: Use a sliding window approach to iterate through all possible substrings of the input string s.
  • Check Semi-Repetitive Property: For each substring, efficiently check if it's semi-repetitive (at most one adjacent pair of the same digit).
  • Maintain Maximum Length: Keep track of the maximum length of semi-repetitive substrings encountered so far.

• Time Complexity: O(n), Space Complexity: O(1)

Code

    def longestSemiRepetitiveSubstring(s: str) -> int:
    """
    Finds the length of the longest semi-repetitive substring of a digit string.

    A string is called semi-repetitive if there is at most one adjacent pair of the same digit.

    Args:
        s: The input digit string.

    Returns:
        The length of the longest semi-repetitive substring of s.
    """

    n = len(s)
    max_len = 0
    for i in range(n):
        for j in range(i, n):
            sub = s[i:j + 1]
            repeats = 0
            for k in range(len(sub) - 1):
                if sub[k] == sub[k + 1]:
                    repeats += 1
            if repeats <= 1:
                max_len = max(max_len, len(sub))
    return max_len