class Solution:
  def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
    ans=[]
    word_list=[]
    cur_len = 0
    for word in words:
      if cur_len + len(word) + len(word_list) > maxWidth:
        spaces = maxWidth - cur_len
        gaps = len(word_list) - 1
        if gaps == 0:
          line = word_list[0] + ' ' * spaces
        else:
          average,left = divmod(spaces,gaps)
          line = ''
          for i in range(gaps):
            line += word_list[i]
            line += average* ' '
            if i<left:
              line +=' '
          line += word_list[-1]
        ans.append(line)
        #initialize
        word_list = []
        cur_len = 0
      word_list.append(word)
      cur_len += len(word)
    #最后一行
    line = ' '.join(word_list)
    spaces = maxWidth - len(line)
    line += ' ' * spaces
    ans.append(line)

    return ans

for i in range(gaps):
  line += word_list[i]
  line += average* ' '
  if i<left:
    line +=' '

class Solution:
  def isSubsequence(self, s: str, t: str) -> bool:
    it = iter(t)
    return all(c in it for c in s)

class Solution:
  def minInsertions(self, s: str) -> int:
    re_str=s[::-1]
    def longestCommonSubsequence(text1: str, text2: str) -> int:
      m = len(text1)
      n = len(text2)

      dp = [[0] * (n + 1) for _ in range(m + 1)]
      for i in range(1, m + 1):
        for j in range(1, n + 1):
          if text1[i - 1] == text2[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
          else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
      return dp[m][n]

    return len(s)-longestCommonSubsequence(s,re_str)

def longestCommonSubsequence(text1: str, text2: str) -> int:
  m = len(text1)
  n = len(text2)

  dp = [[0] * (n + 1) for _ in range(m + 1)]
  for i in range(1, m + 1):
    for j in range(1, n + 1):
      if text1[i - 1] == text2[j - 1]:
        dp[i][j] = dp[i - 1][j - 1] + 1
      else:
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
  return dp[m][n]

class Solution:
  def countValidSelections(self, nums: List[int]) -> int:
    num_sum= sum(nums)
    left_sum = 0
    ans = 0
    right_sum = num_sum
    for num in nums:
      if num == 0:
        if left_sum == right_sum:
          ans+=2
        elif left_sum - right_sum == 1 or right_sum - left_sum == 1:
          ans+=1
      else:
        left_sum+=num
        right_sum=num_sum-left_sum
    return ans

class Solution:
  def twoSum(self, numbers: List[int], target: int) -> List[int]:
    index1=0
    index2=0
    for index,num in enumerate(numbers):
      requirement=target-num
      if requirement in numbers:
        index1=index+1
        if num == requirement:
          index2 = numbers.index(requirement, index1) + 1
          return [index1, index2]
        else:
          index2 = numbers.index(requirement) +1
          return [index1,index2]

class Solution:
  def twoSum(self, numbers: List[int], target: int) -> List[int]:
    left=0
    right=len(numbers)-1
    while left < right:
      cur_sum=numbers[left]+numbers[right]
      if cur_sum==target:
        return [left+1,right+1]
      elif cur_sum < target:
        left+=1
      else:
        right-=1

class Solution:
  def maxArea(self, height: List[int]) -> int:
    max_volume=0
    left=0
    right=len(height)-1
    while(left!=right):
      x=right-left
      y=min(height[left],height[right])
      v=x*y
      if v>max_volume:
        max_volume=v
      if height[left]>=height[right]:
        right-=1
      else:
        left+=1
    return max_volume

class Solution:
  def threeSum(self, nums: List[int]) -> List[List[int]]:
    if len(nums) < 3:
      return []
    sorted_nums = sorted(nums)
    count = 0
    for num in sorted_nums:
      if num < 0:
        count += 1
    nums1 = sorted_nums[:count]
    nums2 = sorted_nums[count:]
    if not nums1 or not nums2:
      if sorted_nums.count(0) >= 3:
        return [[0, 0, 0]]
      return []
    ans = []
    seen = []
    for i in nums1:
      for j in nums2:
        k = -i - j
        if k not in sorted_nums:
          continue
        if [i, j, k].count(i) > sorted_nums.count(i):
          continue
        if [i, j, k].count(j) > sorted_nums.count(j):
          continue
        if [i, j, k].count(k) > sorted_nums.count(k):
          continue

        triple = sorted([i, j, k])
        if triple not in seen:
          seen.append(triple)
          ans.append(triple)

    if sorted_nums.count(0) >= 3:
      ans.append([0, 0, 0])
    return ans

class Solution:
  def threeSum(self, nums: List[int]) -> List[List[int]]:
    ans=[]
    nums.sort()
    n=len(nums)
    for i in range(n-2):
      if i > 0 and nums[i]==nums[i-1]:
        continue
      left=i+1
      right=n-1
      while left < right:
        s = nums[i]+nums[left]+nums[right]
        if s==0:
          ans.append([nums[i],nums[left],nums[right]])
          while left < right and nums[left]==nums[left+1]:
            left+=1
          while left < right and nums[right]==nums[right-1]:
            right-=1
          left+=1
          right-=1
        elif s<0:
          left+=1
        else:
          right-=1
    return ans

class Solution:
  def minSubArrayLen(self, target: int, nums: List[int]) -> int:
    n=len(nums)
    ans=n+1
    s=0
    left=0
    for right,num in enumerate(nums):
      s+=num
      while s>=target:
        ans=min(ans,right-left+1)
        s-=nums[left]
        left+=1
    if ans==n+1:return 0
    return ans

class Solution:
  def lengthOfLongestSubstring(self, s: str) -> int:
    start = 0
    seen = set()
    maxlen = 0

    for end in range(len(s)):
      while s[end] in seen:
        seen.remove(s[start])
        start += 1
      seen.add(s[end])
      maxlen = max(maxlen, end - start + 1)

    return maxlen

class Solution:
  def generate_permutations(self,words:str) -> List[str]:
    if len(words) == 1:
      return words
    res = []
    for i in range(len(words)):
      first = words[i]
      rest = words[:i] + words[i+1:]
      for sub in self.generate_permutations(rest):
        res.append(first + sub)
    return res

  def findSubstring(self, s: str, words: List[str]) -> List[int]:
    sub_words = set(self.generate_permutations(words))
    l=len(s)
    window = len(words[0]) * len(words)
    if window > len(s): return []
    ans=[]
    for start in range(0, len(s) - window + 1):
      if s[start : start + window] in sub_words:
        ans.append(start)
    return ans

class Solution:
  def findSubstring(self, s: str, words: List[str]) -> List[int]:
    if not s or not words:
      return []
    word_len = len(words[0])
    total_len = word_len * len(words)
    word_map = {w: words.count(w) for w in words}
    ans = []
    n = len(s)
    for i in range(0, n - total_len + 1):
      seen = {}
      j = 0
      while j < len(words):
        word_start = i + j * word_len
        word_end = word_start + word_len
        word = s[word_start:word_end]
        if word not in word_map:
          break
        seen[word] = seen.get(word, 0) + 1
        if seen[word] > word_map[word]:
          break
        j += 1
      if j == len(words):
        ans.append(i)
    return ans

class Solution:
  def findSubstring(self, s: str, words: List[str]) -> List[int]:
    if not s or not words:
      return []
    word_len = len(words[0])
    total_len = word_len * len(words)
    word_map = {w: words.count(w) for w in words}
    ans = []
    n = len(s)
    for offset in range(word_len):
      left = offset
      seen = {}
      count = 0
      for right in range(offset, n - word_len + 1, word_len):
        word = s[right:right+word_len]
        if word in word_map:
          seen[word] = seen.get(word, 0) + 1
          count += 1
          while seen[word] > word_map[word]:
            left_word = s[left:left+word_len]
            seen[left_word] -= 1
            left += word_len
            count -= 1
          if count == len(words):
            ans.append(left)
        else:
          seen.clear()
          count = 0
          left = right + word_len
    return ans

class Solution:
  def findSubstring(self, s: str, words: List[str]) -> List[int]:
    n = len(s)
    step = len(words[0])
    total_len = step * len(words)
    res = []
    for i in range(step):
      map_word_cnt = {}
      for word in words:
        if word not in map_word_cnt:
          map_word_cnt[word] = 1
        else:
          map_word_cnt[word] += 1
      match_cnt = len(words)
      right = i
      while right + step - 1 < n:
        left = right + step - total_len
        left_out = left - step
        if left_out >= 0:
          w_left_out = s[left_out:left_out+step]
          if w_left_out in map_word_cnt:
            map_word_cnt[w_left_out] += 1
            if map_word_cnt[w_left_out] > 0:
              match_cnt += 1
        w_right = s[right:right+step]
        if w_right in map_word_cnt:
          map_word_cnt[w_right] -= 1
          if map_word_cnt[w_right] >= 0:
            match_cnt -= 1
        if left >= 0 and match_cnt == 0:
          res.append(left)
        right += step
    return res

class Solution:
  def count(self, t: str) -> dict:
    t_count = {}
    for char in t:
      if char in t_count:
        t_count[char] += 1
      else:
        t_count[char] = 1
    return t_count

  def check(self, current_dict: dict, t_count: dict) -> bool:
    for char, required_count in t_count.items():
      if current_dict.get(char, 0) < required_count:
        return False
    return True

  def minWindow(self, s: str, t: str) -> str:
    t_count = self.count(t)
    window_counts = {}
    left = 0
    min_len = len(s) + 1
    result = ""

    for right in range(len(s)):
      char_in = s[right]
      window_counts[char_in] = window_counts.get(char_in, 0) + 1

      while self.check(window_counts, t_count):
        current_len = right - left + 1
        if current_len < min_len:
          min_len = current_len
          result = s[left : right + 1]

        char_out = s[left]
        window_counts[char_out] -= 1

        if window_counts[char_out] == 0:
          del window_counts[char_out]

        left += 1
    return result

def check(self, current_dict: dict, t_count: dict) -> bool:
  for char, required_count in t_count.items():
    if current_dict.get(char, 0) < required_count:
      return False
  return True

class Solution:
  def minWindow(self, s: str, t: str) -> str:
    need=defaultdict(int)
    for c in t:
      need[c]+=1
    needCnt=len(t)
    i=0
    res=(0,float('inf'))
    for j,c in enumerate(s):
      if need[c]>0:
        needCnt-=1
      need[c]-=1
      if needCnt==0:
        while True:
          c=s[i]
          if need[c]==0:
            break
          need[c]+=1
          i+=1
        if j-i<res[1]-res[0]:
          res=(i,j)
        need[s[i]]+=1
        needCnt+=1
        i+=1
    return ''if res[1]>len(s) else s[res[0]:res[1]+1]

class Solution:
  def isValidSudoku(self, board: List[List[str]]) -> bool:
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]

    for i in range(0,9):
      for j in range(0,9):
        num = board[i][j]
        if num == '.':
          continue
        if num in rows[i]:
          return False
        rows[i].add(num)
        if num in cols[j]:
          return False
        cols[j].add(num)

        box_index = (i // 3) * 3 + (j // 3)
        if num in boxes[box_index]:
          return False
        boxes[box_index].add(num)
    return True

class Solution:
  def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
    if not matrix or not matrix[0]:
      return []
    ans = []
    num_rows = len(matrix)
    num_cols = len(matrix[0])

    left, right = 0, num_cols - 1
    top, bottom = 0, num_rows - 1

    while left <= right and top <= bottom:
      for col in range(left, right + 1):
        ans.append(matrix[top][col])
      top += 1
      for row in range(top, bottom + 1):
        ans.append(matrix[row][right])
      right -= 1
      if not (left <= right and top <= bottom):
        break
      for col in range(right, left - 1, -1):
        ans.append(matrix[bottom][col])
      bottom -= 1
      for row in range(bottom, top - 1, -1):
        ans.append(matrix[row][left])
      left += 1
    return ans

class Solution:
  def rotate(self, matrix: List[List[int]]) -> None:
    matrix[:] = list(map(list, zip(*matrix)))
    for row in matrix: row.reverse()

class Solution:
  def setZeroes(self, matrix: List[List[int]]) -> None:
    """
    Do not return anything, modify matrix in-place instead.
    """
    rows = len(matrix)
    cols = len(matrix[0])
    temp = []
    for i in range(rows):
      for j in range(cols):
        if matrix[i][j] == 0:
          temp.append([i, j])

    for r, c in temp:
      for j in range(cols):
        matrix[r][j] = 0
      for i in range(rows):
        matrix[i][c] = 0

class Solution:
  def setZeroes(self, matrix: List[List[int]]) -> None:
    m, n = len(matrix), len(matrix[0])
    flag_col0 = False

    for i in range(m):
      if matrix[i][0] == 0:
        flag_col0 = True
      for j in range(1, n):
        if matrix[i][j] == 0:
          matrix[i][0] = matrix[0][j] = 0

    for i in range(m - 1, -1, -1):
      for j in range(1, n):
        if matrix[i][0] == 0 or matrix[0][j] == 0:
          matrix[i][j] = 0
      if flag_col0:
        matrix[i][0] = 0

class Solution:
  def gameOfLife(self, board: List[List[int]]) -> None:
    """
    Do not return anything, modify board in-place instead.
    """
    m, n = len(board), len(board[0])
    neighbors = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]
    for i in range(m):
      for j in range(n):
        alive = 0
        for dx, dy in neighbors:
          r, c = i + dx, j + dy
          if 0 <= r < m and 0 <= c < n:
            if board[r][c] == 1 or board[r][c] == 2:
              alive += 1
        if board[i][j] == 1 and (alive < 2 or alive > 3):
          board[i][j] = 2
        elif board[i][j] == 0 and alive == 3:
          board[i][j] = 3

    for i in range(m):
      for j in range(n):
        if board[i][j] == 2:
          board[i][j] = 0
        elif board[i][j] == 3:
          board[i][j] = 1

class Solution:
  def canConstruct(self, ransomNote: str, magazine: str) -> bool:
    if len(ransomNote) > len(magazine):
      return False
    magazine_counts = Counter(magazine)

    for char in ransomNote:
      if magazine_counts[char] > 0:
        magazine_counts[char] -= 1
      else:
        return False

    return True

class Solution:
  def canConstruct(self, ransomNote: str, magazine: str) -> bool:
    if len(ransomNote)>len(magazine) or len(set(magazine)) < len(set(ransomNote)):
      return False
    count = {}
    for i in magazine:
      count[i] = count.get(i,0)+1
    for i in ransomNote:
      if count.get(i, 0) == 0:
        return False
      count[i] -= 1
    return True

class Solution:
  def isIsomorphic(self, s: str, t: str) -> bool:
    if len(s)!=len(t):
      return False
    s2tdict={}
    t2sdict={}
    for sstr,tstr in zip(s,t):
      if sstr in s2tdict and s2tdict[sstr]!=tstr:
        return False
      if tstr in t2sdict and t2sdict[tstr]!=sstr:
        return False
      s2tdict[sstr]=tstr
      t2sdict[tstr]=sstr
    return True

class Solution:
  def isIsomorphic(self, s: str, t: str) -> bool:
    return len(set(s)) == len(set(t)) == len(set(zip(s, t)))

class Solution:
  def wordPattern(self, pattern: str, s: str) -> bool:
    s2list=s.split(" ")
    p2list=list(pattern)
    return len(s2list)==len(p2list) and len(set(zip(s2list,p2list)))==len(set(s2list))==len(set(p2list))

class Solution:
  def isAnagram(self, s: str, t: str) -> bool:
    s2list=list(s)
    t2list=list(t)
    scounter=Counter(s2list)
    tcounter=Counter(t2list)
    if scounter==tcounter:
      return True
    return False

class Solution:
  def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
    anagram_map = defaultdict(list)
    for s in strs:
      sorted_s=str(sorted(s))
      anagram_map[sorted_s].append(s)

    return list(anagram_map.values())

class Solution:
  def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
    if len(strs) == 1:
      return [strs]
    ans= {}
    for ss in strs:
      s = str(sorted(ss))
      if s not in ans :
        ans[s] = [ss]
      else :
        ans[s].append(ss)

    return list(ans.values())

class Solution:
  def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
    mp = collections.defaultdict(list)

    for str in strs:
      key=''.join(sorted(str))
      mp[key].append(str)

    return list(mp.values())

class Solution:
  def twoSum(self, nums: List[int], target: int) -> List[int]:
    num_map = {}
    for i, num in enumerate(nums):
      complement = target - num
      if complement in num_map:
        return [num_map[complement], i]
      num_map[num] = i
    return []Q