leetcode 1763(브루트포스), 1099(two pointer), 395(구현), 1071(구현)

1763 https://leetcode.com/problems/longest-nice-substring/
easy 로 분류되었는데 medium 하위정도 되는것같다. O(n^2)으로 모든 경우를 탐색한다. 길게 좌우에서 조여오면서 탐색한다.
cur_s는 l과 r이 움직임에 따라 만들어지는 부분적인 문자열이고, cur_s내의 모든 문자가 대문자와 소문자가 cur_s내에 존재해야 하면서 이게 이전 길이보다 더 길면 바꿔준다.

class Solution:
    def longestNiceSubstring(self, s: str) -> str:
        len_s = len(s)
        l = 0
        ret = ''
        while l < len_s:
            r = len_s - 1
            while l < r:
                cur_s = s[l:r+1]
                if all(ss.lower() in cur_s and ss.upper() in cur_s for ss in cur_s) and \
                   len(ret) < r - l + 1:
                    ret = cur_s
                r -= 1
            l += 1
        return ret

 

1099 https://leetcode.com/problems/two-sum-less-than-k/

class Solution:
    def twoSumLessThanK(self, nums: List[int], k: int) -> int:
        nums.sort()
        l,r = 0, len(nums)-1
        ret = 0
        while l < r:
            if nums[l] + nums[r] < k:
                ret = max(ret, nums[l] + nums[r])
                l += 1
            else:
                r -= 1
        return ret if ret != 0 else -1

 

395 https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        queue = [s]
        visited = set()
        ret = 0
        while queue:
            p = queue.pop(0)
            p_dict = Counter(p)
            if all(p_dict[key] >= k for key in p_dict.keys()):  # 현재 쪼개진 문자열 p가 조건에 부합하면 저장
                ret = max(ret, sum(p_dict.values()))
                continue
            for key in p_dict.keys():  # 문자열을 돌면서
                if p_dict[key] < k:  # 조건에 맞지 않으면 그 문자열을 대상으로 나눔
                    for each in p.split(key):
                        if each not in visited:
                            visited.add(each)
                            queue.append(each)
        return ret

개인적으로 아래 코드가 가장 깔끔한것 같다
https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/discuss/704604/Python-3Longest-Substring-with-Atleast-K-repeating-characters.-Beats-85.

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        if len(s)==0:
            return 0
        
        cnt = collections.Counter(s)
        for i in cnt:
            if cnt[i] < k:
                return max(self.longestSubstring(p,k) for p in s.split(i))
        return len(s)

 

1071 https://leetcode.com/problems/greatest-common-divisor-of-strings/

왠지 LCS(longest common subsequence)와 비슷하지만 lcs와는 다른게 반복해서 str1과 str2를 만들수 있어야 한다는거다. 그냥 구현하면 된다.

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        len_s1, len_s2 = len(str1), len(str2)
        ret = ''
        for i in range(1, min(len_s1, len_s2) + 1):
            if len_s1 % i == 0 and len_s2 % i == 0:
                temp = str2[:i]
                if temp*(len_s1//i) == str1 and temp*(len_s2//i) == str2:
                    ret = temp
        return ret