Find the Longest Semi-Repetitive Substring — LeetCode 2730 Python Solution
MediumStringSliding Window
- Problem
- #2730
- Pattern
- Sliding Window
- Reading time
- 2 min
- Source
- leetcode.com
The 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.
Python solution
Python
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 ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n), where n is the length of the string |
| Space | O(1) auxiliary |
Pattern: Sliding Window
Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 2730. Find the Longest Semi-Repetitive Substring is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.
The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.
Related problems
LeetCode 1044Longest Duplicate SubstringHardLeetCode 1208Get Equal Substrings Within BudgetMediumLeetCode 1234Replace the Substring for Balanced StringMediumLeetCode 1456Maximum Number of Vowels in a Substring of Given LengthMediumLeetCode 1839Longest Substring Of All Vowels in OrderMediumLeetCode 1871Jump Game VIIMedium
Frequently asked questions
- How hard is LeetCode 2730. Find the Longest Semi-Repetitive Substring?
- LeetCode 2730. Find the Longest Semi-Repetitive Substring is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2730. Find the Longest Semi-Repetitive Substring?
- The Python solution on this page runs in O(n), where n is the length of the string.
- What is the space complexity of LeetCode 2730. Find the Longest Semi-Repetitive Substring?
- The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 2730. Find the Longest Semi-Repetitive Substring cover?
- LeetCode 2730. Find the Longest Semi-Repetitive Substring is tagged String and Sliding Window on LeetCode.