Leetcode 1156. Swap For Longest Repeated Character Substring

Problem statement

https://leetcode.com/problems/swap-for-longest-repeated-character-substring/

Solution

Here we can use functionality of python: we need to find either one full group and add element to the end if possible (for this we keep counter of all elements) or we need to have two groups of same value, where between we have another element with frequency 1.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def maxRepOpt1(self, S):
        A = [[c, len(list(g))] for c, g in groupby(S)]
        cnt = Counter(S)
        res = max(min(k + 1, cnt[c]) for c, k in A)
        for (v0, f0), (v1, f1), (v2, f2) in zip(A, A[1:], A[2:]):
            if v0 == v2 and f1 == 1:
                res = max(res, min(f0 + f2 + 1, cnt[v0]))
        return res