Difficulty - Medium

from typing import List


class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums = sorted(nums)
        ans = []
        for i in range(len(nums) - 2):
            if i == 0 or nums[i] > nums[i - 1]:
                l = i + 1
                r = len(nums) - 1
                while l < r:
                    if nums[i] + nums[l] + nums[r] == 0:
                        ans.append([nums[i], nums[l], nums[r]])
                        l += 1
                        r -= 1
                        while l < r and nums[l] == nums[l - 1]:
                            l += 1
                        while l < r and nums[r] == nums[r + 1]:
                            r -= 1
                    elif nums[i] + nums[l] + nums[r] > 0:
                        while l < r:
                            r -= 1
                            if nums[r] < nums[r + 1]:
                                break
                    else:
                        while l < r:
                            l += 1
                            if nums[l] > nums[l - 1]:
                                break

        return ans

from typing import List


class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        ans = 0
        mid = nums[len(nums) // 2]
        min_diff = abs(nums[0] + mid + nums[len(nums) - 1] - target)

        for i in range(len(nums) - 2):
            l = i + 1
            r = len(nums) - 1
            while l < r:
                value = nums[i] + nums[l] + nums[r]
                if value == target:
                    return target
                diff = abs(value - target)
                if diff <= min_diff:
                    min_diff = diff
                    ans = value
                if value > target:
                    r -= 1
                if value < target:
                    l += 1

        return ans

from typing import List


class Solution:
    def maxArea(self, height: List[int]) -> int:
        size = len(height)
        l = 0
        r = size - 1
        maxWater = 0
        while l < r:
            water = (r - l) * min(height[l], height[r])
            if water > maxWater:
                maxWater = water

            if height[l] < height[r]:
                l = l + 1
            else:
                r = r - 1

        return maxWater

class Solution:
    def intToRoman(self, num: int) -> str:
        value = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
        roman = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
        ans = ""
        for i in range(len(value)):
            while num >= value[i]:
                num -= value[i]
                ans += roman[i]

        return ans

from typing import List


class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if digits == "":
            return []

        phone_dict = {
            "2": ["a", "b", "c"],
            "3": ["d", "e", "f"],
            "4": ["g", "h", "i"],
            "5": ["j", "k", "l"],
            "6": ["m", "n", "o"],
            "7": ["p", "q", "r", "s"],
            "8": ["t", "u", "v"],
            "9": ["w", "x", "y", "z"],
        }

        def dfs(num, string, result):
            if num == length:
                result.append(string)
                return
            for letter in phone_dict[digits[num]]:
                dfs(num + 1, string + letter, result)

        result = []

        length = len(digits)
        dfs(0, "", result)

        return result

class Solution:
    def findPalindrome(self, s: str, l: int, r: int) -> str:
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return s[l + 1 : r]

    def longestPalindrome(self, s: str) -> str:
        result = ""
        for i in range(len(s)):
            # ABA
            type1 = self.findPalindrome(s, i, i)
            if len(type1) > len(result):
                result = type1
            # ABBA
            type2 = self.findPalindrome(s, i, i + 1)
            if len(type2) > len(result):
                result = type2

        return result

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_len = 0
        substr = ""
        rear = 0

        for front in range(len(s)):
            if s[front] not in substr:
                substr += s[front]
            else:
                max_len = max(max_len, len(substr))
                while s[rear] != s[front]:
                    rear += 1
                rear += 1
                substr = s[rear : front + 1]

        return max(max_len, len(substr))

class Solution:
    def reverse(self, x: int) -> int:
        digits = str(x)[::-1]
        ans = int(digits) if x >= 0 else int(digits[:-1])
        if ans > 2**31:
            ans = 0

        return ans if x > -0 else -ans

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s

        rows = []
        a = 2 * numRows - 2
        for i in range(a):
            rows.append([])

        for i in range(len(s)):
            ind = i % a
            if ind >= numRows:
                ind = a - ind
            rows[ind].append(s[i])

        result = ""
        for i in range(a):
            result += "".join(rows[i])

        return result