[Mock] Microsoft 12

1470. Shuffle the Array

Given the array nums consisting of 2n elements in the form [x1,x2,...,xn,y1,y2,...,yn].

Return the array in the form [x1,y1,x2,y2,...,xn,yn].

My Answer 1: Accepted (Runtime: 60 ms - 68.94% / Memory Usage: 14.2 MB - 98.47%)

class Solution:
    def shuffle(self, nums: List[int], n: int) -> List[int]:
        ans = []
        for i, j in zip(nums[:n], nums[n:]):
            ans.append(i)
            ans.append(j)
        
        return ans

nums 를 반 나눠서 각각 번갈아가면서 ans 에 저장

---

1156. Swap For Longest Repeated Character Substring

Given a string text, we are allowed to swap two of the characters in the string. Find the length of the longest substring with repeated characters.

My Answer 1: Wrong Answer (45 / 53 test cases passed.)

class Solution:
    def maxRepOpt1(self, text: str) -> int:
        lists = list(text)
        start = 0
        last = 0
        ans = 0
        for i in range(len(lists)-1):
            if lists[i] != lists[i+1]:
                last = i+1
                for j in range(i+2, len(lists)):
                    if lists[i] == lists[j]:
                        last = j
                    else:
                        break
                if lists[i] in lists[last+1:]:
                    ans = max(ans, last - start + 1)
                else:
                    ans = max(ans, last - start)
                start = i+1
        if ans == 0:
            return len(text)
        
        return ans

(굳이 list 로 바꾸지 않아도 됨)

연속되던 문자가 끊길 경우 => if lists[i] != lists[i+1]:
반복문 하나 더 돌려서 lists[i+1] 뒤에서 다시 연속하는지 확인해서 last update

ex) "ababa" => 첫번째 b 뒤에 a 가 얼만큼 연속되는지 확인
(첫번째 b 와 마지막 a 를 swap 했을 때 최대 길이 3 을 return 하기 위해)

다시 끊기는 지점에서 break 후 빠져나와서 길이 계산

두번째 끊기는 지점 이후에 연속되던 문자가 또 있는 경우
=> 그것과 swap 하면 되니까 start ~ last 길이 return
없을 경우
=> start ~ last 길이 - 1 return

문자열 전체가 반복되는 문자열일 경우 ans = 0 이므로 전제 길이 return

그런데... "bbababaaaa" 의 경우는 ba 를 반복 문자열로 보는 듯...
문자 하나의 반복으로만 생각해서 실패...~~

다른 아이디어

1. 재귀로 substring 을 구해서 반복되는지 확인하면 되지 않을까 했는데..
   문자끼리 한번 swap 을 어떻게 적용해야할지...

for i in range(len(text)):
      for j in range(i+1, len(text)):
            func(i, text[:i]+text[j]+text[i+1:j]+text[i]+text[j+1:])

이런 식으로 아예 한번씩 swap 시켜서 반복되는 substring 을 찾아주는 함수로 넘기기

시간 없어서 구현은 못함..^^

Solution 1: Accepted (Runtime: 68 ms - 64.98% / Memory Usage: 15.9 MB - 27.08%)

class Solution:
    def maxRepOpt1(self, text: str) -> int:
        # We get the group's key and length first, e.g. 'aaabaaa' -> [[a , 3], [b, 1], [a, 3]
        A = [[c, len(list(g))] for c, g in itertools.groupby(text)]
        # We also generate a count dict for easy look up e.g. 'aaabaaa' -> {a: 6, b: 1}
        count = collections.Counter(text)
        # only extend 1 more, use min here to avoid the case that there's no extra char to extend
        res = max(min(k + 1, count[c]) for c, k in A)
        # merge 2 groups together
        for i in range(1, len(A) - 1):
            # if both sides have the same char and are separated by only 1 char
            if A[i - 1][0] == A[i + 1][0] and A[i][1] == 1:
                # min here serves the same purpose
                res = max(res, min(A[i - 1][1] + A[i + 1][1] + 1, count[A[i + 1][0]]))
        return res

groupby 이용해서 그룹화
ex) "bbababaaaa" => A = [['b', 2], ['a', 1], ['b', 1], ['a', 1], ['b', 1], ['a', 4]]

res = max(min(k + 1, count[c]) for c, k in A)
=> swap 이 가능하면 k+1 아니면 count[c]

<for 문>
if A[i - 1][0] == A[i + 1][0] and A[i][1] == 1:
=> 연결이 끊기는 지점 앞 뒤로 같은지 확인 & 앞뒤의 사이값의 길이가 1 인지 확인

A[i - 1][1] + A[i + 1][1] + 1 => swap 해서 길이 + 1
count[A[i + 1][0]] => no swap

groupby 예시

[k for k, g in groupby('AAAABBBCCDAABBB')] --> A B C D A B
[list(g) for k, g in groupby('AAAABBBCCD')] --> AAAA BBB CC D

Solution 2: Accepted (Runtime: 72 ms - 51.62% / Memory Usage: 14.6 MB - 63.18%)

class Solution:
    def maxRepOpt1(self, text: str) -> int:
        res = 0
        count = collections.Counter()
        countChar = collections.Counter(text)
        start = 0
        maxCount = 0
        maxChar = text[0]
        
        for right in range(len(text)):
            count[text[right]] += 1
            if count[text[right]] > maxCount:
                maxChar = text[right]
                maxCount = count[text[right]]            
            if right-start+1 - maxCount > 1:
                count[text[start]] -= 1
                start += 1
            res = max(res,right-start+1)
            
        return min(res,countChar[maxChar])

Sliding Window 라는데... 모르겠읍니다..