[Leetcode] 2730. Find the Longest Semi-Repetitive Substring (Medium)

概述

題目

https://leetcode.com/problems/find-the-longest-semi-repetitive-substring/
找出一個最多出現一次相鄰字元相等的最長字串，若是沒有相鄰字元也成立

心得

週賽做最久、吃最多 bug 才 AC 的題目，原因一開始根本沒把題目讀懂，讀題的時候自動忽略了 consecutive 是相鄰的意思，看測資自行理解成最長只有 2 個相同字元的字串，所以用雙指針做、花了一堆時間，最後才發現根本不是這麼一回事 QQ，後續用記位置的方式 AC

Array

思路

先記下有出現相鄰字元相等的前一個字元位置，再補上首、尾作為參考點，最後兩兩 (中間有空一數，代表真正要相鄰的那組) 相減確認最長字串為何

程式

class Solution(object):
    def longestSemiRepetitiveSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)

        # 紀錄相鄰相等字元的第一位位置
        arr = [-1]
        for i in range(n-1):
            if s[i] == s[i+1]:
                arr.append(i)
        arr.append(n-1)

        # 無相鄰相等字元
        if len(arr) == 2:
            return n

        # 有相鄰相等字元，求最大，跳過者為該組字串的相鄰組
        mxv = 0
        for i in range(len(arr)-2):
            mxv = max(mxv, arr[i+2]-arr[i])
        return mxv

Complexity

Time Complexity: O(n)
只有掃過 2 次 n 個數

Space Complexity: O(n)
記位置最大要記 n 個

Extend

思路

將每個相鄰相等的字串進行左右展延，最後求最大長度

程式

class Solution(object):
    def longestSemiRepetitiveSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)

        # 紀錄相鄰相等字元的第一位位置
        arr = []
        for i in range(n-1):
            if s[i] == s[i+1]:
                arr.append(i)
        
        mxv = 0
        for i in arr:
        	# 展延啟始位置
            j = i+2
            i -= 1

            # 向左展延
            cnt = 2
            while i > -1 and s[i] != s[i+1]:
                cnt += 1
                i -= 1
            
            # 向右展延
            while j < n and s[j] != s[j-1]:
                cnt += 1
                j += 1
            
            # 比較長度
            mxv = max(mxv, cnt)
        
        # 若 arr 為空則表無相鄰相等，回傳總長
        return mxv if mxv else n

Complexity

Time Complexity: O(n^2)
只有掃過 n 個數，每次向左、向右延展，可能會做到 n 次，故為 O(n^2)

Space Complexity: O(n)
記位置最大要記 n 個

Two Pointer

思路

透過雙指針來找到符合題意的最長字串

程式

class Solution(object):
    def longestSemiRepetitiveSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)
        mxv = 1
        pre = 0
        dup = 0

        # 雙指針
        for cur in range(n):
            if cur == 0:
                continue
            if s[cur] == s[cur-1]:
                pre = dup
                dup = cur
            mxv = max(mxv, cur-pre+1)
        return mxv