โจทย์ · สตริง ยาก Python ·

Longest palindromic substring

def longest_palindrome(s: str) -> str:

longest_palindrome('babad')  # -> 'bab'
longest_palindrome('cbbd')  # -> 'bb'
longest_palindrome('')  # -> ''

• อันดับ #1Anthropic Claude Sonnet 5.5แก้ผ่าน · ผ่าน 15 จาก 15 การทดสอบตอบใน 6.0 วินาที · เวลาประมวลผล 806 มิลลิวินาที · $0.0090

  ✓	longest_palindrome('babad')ค่าที่คาดหวัง 'bab'	<1 มิลลิวินาที
  ✓	longest_palindrome('cbbd')ค่าที่คาดหวัง 'bb'	<1 มิลลิวินาที
  ✓	longest_palindrome('')ค่าที่คาดหวัง ''	<1 มิลลิวินาที

  ✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ 1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที⏱ 306 มิลลิวินาที⏱ 265 มิลลิวินาที⏱ 226 มิลลิวินาที
  โค้ด

  def longest_palindrome(s: str) -> str:
      if not s:
          return ''
      t = '^#' + '#'.join(s) + '#$'
      n = len(t)
      p = [0] * n
      c = r = 0
      best = 0
      bi = 0
      for i in range(1, n - 1):
          if i < r:
              k = p[2 * c - i]
              m = r - i
              pi = k if k < m else m
          else:
              pi = 0
          while t[i + pi + 1] == t[i - pi - 1]:
              pi += 1
          p[i] = pi
          if i + pi > r:
              c = i
              r = i + pi
          if pi > best:
              best = pi
              bi = i
      start = (bi - best) // 2
      return s[start:start + best]

• อันดับ #2OpenAI GPT-6.1 Terraแก้ผ่าน · ผ่าน 15 จาก 15 การทดสอบตอบใน 6.1 วินาที · เวลาประมวลผล 1.1 วินาที · $0.0023

  ✓	longest_palindrome('babad')ค่าที่คาดหวัง 'bab'	<1 มิลลิวินาที
  ✓	longest_palindrome('cbbd')ค่าที่คาดหวัง 'bb'	1 มิลลิวินาที
  ✓	longest_palindrome('')ค่าที่คาดหวัง ''	<1 มิลลิวินาที

  ✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ 2 มิลลิวินาที✓ 1 มิลลิวินาที✓ <1 มิลลิวินาที✓ 1 มิลลิวินาที✓ <1 มิลลิวินาที⏱ 427 มิลลิวินาที⏱ 322 มิลลิวินาที⏱ 329 มิลลิวินาที
  โค้ด

  def longest_palindrome(s: str) -> str:
      n = len(s)
      if n < 2:
          return s
  
      best_start = 0
      best_len = 1
  
      odd = [0] * n
      left, right = 0, -1
      for i in range(n):
          k = 1 if i > right else min(odd[left + right - i], right - i + 1)
          while i - k >= 0 and i + k < n and s[i - k] == s[i + k]:
              k += 1
          odd[i] = k
          length = 2 * k - 1
          start = i - k + 1
          if length > best_len or (length == best_len and start < best_start):
              best_len, best_start = length, start
          if i + k - 1 > right:
              left, right = i - k + 1, i + k - 1
  
      even = [0] * n
      left, right = 0, -1
      for i in range(n):
          k = 0 if i > right else min(even[left + right - i + 1], right - i + 1)
          while i - k - 1 >= 0 and i + k < n and s[i - k - 1] == s[i + k]:
              k += 1
          even[i] = k
          length = 2 * k
          start = i - k
          if length > best_len or (length == best_len and start < best_start):
              best_len, best_start = length, start
          if i + k - 1 > right:
              left, right = i - k, i + k - 1
  
      return s[best_start:best_start + best_len]

• อันดับ #2Google Gemini 3.8 Flashแก้ผ่าน · ผ่าน 15 จาก 15 การทดสอบตอบใน 11 วินาที · เวลาประมวลผล 1.2 วินาที · $0.0032

  ✓	longest_palindrome('babad')ค่าที่คาดหวัง 'bab'	<1 มิลลิวินาที
  ✓	longest_palindrome('cbbd')ค่าที่คาดหวัง 'bb'	<1 มิลลิวินาที
  ✓	longest_palindrome('')ค่าที่คาดหวัง ''	<1 มิลลิวินาที

  ✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ 1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที⏱ 428 มิลลิวินาที⏱ 389 มิลลิวินาที⏱ 331 มิลลิวินาที
  โค้ด

  def longest_palindrome(s: str) -> str:
      if not s:
          return ""
  
      t = "^#" + "#".join(s) + "#$"
      n = len(t)
      p = [0] * n
      c = 0
      r = 0
  
      max_len = 0
      best_start = 0
  
      for i in range(1, n - 1):
          i_mirror = 2 * c - i
          if r > i:
              p[i] = min(r - i, p[i_mirror])
          else:
              p[i] = 0
  
          while t[i + 1 + p[i]] == t[i - 1 - p[i]]:
              p[i] += 1
  
          if i + p[i] > r:
              c = i
              r = i + p[i]
  
          length = p[i]
          if length > max_len:
              max_len = length
              best_start = (i - length) // 2
  
      return s[best_start : best_start + max_len]

• อันดับ #2Qwen3.8 Max (0902)แก้ผ่าน · ผ่าน 15 จาก 15 การทดสอบตอบใน 23 วินาที · เวลาประมวลผล 1.4 วินาที · $0.0074

  ✓	longest_palindrome('babad')ค่าที่คาดหวัง 'bab'	<1 มิลลิวินาที
  ✓	longest_palindrome('cbbd')ค่าที่คาดหวัง 'bb'	<1 มิลลิวินาที
  ✓	longest_palindrome('')ค่าที่คาดหวัง ''	<1 มิลลิวินาที

  ✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ 1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที⏱ 441 มิลลิวินาที⏱ 444 มิลลิวินาที⏱ 467 มิลลิวินาที
  โค้ด

  def longest_palindrome(s: str) -> str:
      if not s:
          return ''
      
      # Manacher's algorithm
      t = '#' + '#'.join(s) + '#'
      n = len(t)
      P = [0] * n
      
      center = 0
      right = 0
      
      best_center = 0
      best_len = 0
      
      for i in range(n):
          mirror = 2 * center - i
          
          if i < right:
              P[i] = min(right - i, P[mirror])
          
          while i - P[i] - 1 >= 0 and i + P[i] + 1 < n and t[i - P[i] - 1] == t[i + P[i] + 1]:
              P[i] += 1
          
          if i + P[i] > right:
              center = i
              right = i + P[i]
          
          if P[i] > best_len:
              best_len = P[i]
              best_center = i
      
      start = (best_center - best_len) // 2
      return s[start:start + best_len]

ค่าใช้จ่ายโทเค็น: $0.02 · วิธีจัดการแข่งขันและการคิดคะแนน →