โปรแกรม Python หา Substring ยาวสุดระหว่างตัวอักษรซ้ำกัน

กำหนด String s หาความยาวของ Substring ยาวสุดที่อยู่ ระหว่าง ตัวอักษรตัวเดียวกัน 2 ตัว (ไม่นับตัวอักษรทั้งสองตัว) หากไม่มีคืน -1

ตัวอย่าง

• Input: s = "level"
• Output: 3

Positions of 'l': 0, 3 → Substring between = "eve" (length 3)
Positions of 'e': 1, 2 → Substring between = "" (length 0)
Max = 3

อัลกอริธึม: เก็บ First และ Last Occurrence

1. สร้าง Dictionary เก็บ Index แรกและสุดท้ายของแต่ละ Character
2. สำหรับแต่ละ Char ที่ปรากฏ ≥ 2 ครั้ง: คำนวณ last_index - first_index - 1
3. หาค่า Max

โค้ด Python

def max_length_between_equal_chars(s):
    """
    หาความยาว Substring ยาวสุดระหว่างตัวอักษรซ้ำกัน 2 ตัว
    
    Args:
        s: str - Input String
    
    Returns:
        int - ความยาวสูงสุด (ไม่นับตัวอักษรปลาย), -1 หากไม่มี
    """
    first_occurrence = {}
    last_occurrence = {}
    
    for i, char in enumerate(s):
        if char not in first_occurrence:
            first_occurrence[char] = i
        last_occurrence[char] = i  # อัปเดตทุกครั้ง → เก็บ Index สุดท้าย
    
    max_len = -1
    for char in first_occurrence:
        if first_occurrence[char] != last_occurrence[char]:  # ปรากฏ ≥ 2 ครั้ง
            length = last_occurrence[char] - first_occurrence[char] - 1
            max_len = max(max_len, length)
    
    return max_len


# ทดสอบ
if __name__ == "__main__":
    test_cases = [
        ("level", 3),      # l...l = "eve" (3)
        ("abca", 2),       # a...a = "bc" (2)
        ("aa", 0),         # a...a = "" (0)
        ("abc", -1),       # ไม่มีซ้ำ
        ("abccba", 4),     # a...a = "bccb" (4) หรือ c...c = "cb" (2) → max=4
        ("a", -1),         # Single char
        ("", -1),          # Empty string
        ("ababa", 3),      # a...a (index 0,4) = "bab" (3)
    ]
    
    for s, expected in test_cases:
        result = max_length_between_equal_chars(s)
        status = "✓" if result == expected else "✗"
        print(f"{status} '{s}' => {result} (expected {expected})")

ผลลัพธ์

✓ 'level' => 3 (expected 3)
✓ 'abca' => 2 (expected 2)
✓ 'aa' => 0 (expected 0)
✓ 'abc' => -1 (expected -1)
✓ 'abccba' => 4 (expected 4)
✓ 'a' => -1 (expected -1)
✓ '' => -1 (expected -1)
✓ 'ababa' => 3 (expected 3)

Complexity Analysis

• Time: O(n) - Single Pass
• Space: O(min(n, Σ)) โดย Σ = Alphabet Size (26 สำหรับ Lowercase)

วิธีอื่น: Single Pass (เก็บ First Index เท่านั้น)

def max_length_between_equal_chars_v2(s):
    first_index = {}
    max_len = -1
    
    for i, char in enumerate(s):
        if char in first_index:
            # เจอซ้ำ: คำนวณระยะห่างจากครั้งแรก
            length = i - first_index[char] - 1
            max_len = max(max_len, length)
        else:
            first_index[char] = i
    
    return max_len

LeetCode Reference

Problem 1624: "Largest Substring Between Two Equal Characters" - Easy