Python Program: หาตัวอักษรแรกที่ไม่ซ้ำใน Stream (First Non-Repeating Character)

หาตัวอักษรที่ไม่ซ้ำ (Unique/Non-repeating) ตัวแรกจาก String หรือ Stream ของ Characters มีหลายวิธีแก้ เราจะสาธิต 2 วิธี

วิธีที่ 1: ใช้ Dictionary + List (O(n) Time, O(n) Space)

นับ Frequency แล้ว Scan หาตัวแรกที่ Count = 1

def first_non_repeating_char(s: str):
    char_order = []      # เก็บลำดับตัวอักษรที่เจอ
    counts = {}          # นับ Frequency
    
    for c in s:
        if c in counts:
            counts[c] += 1
        else:
            counts[c] = 1
            char_order.append(c)
    
    # หาตัวแรกที่ Count == 1
    for c in char_order:
        if counts[c] == 1:
            return c
    return None

# ทดสอบ
print(first_non_repeating_char('PythonforallPythonMustforall'))  # M
print(first_non_repeating_char('tutorialspointfordeveloper'))    # u
print(first_non_repeating_char('AABBCC'))                         # None

ผลลัพธ์

M
u
None

วิธีทำงาน: Loop ผ่าน String 1 ครั้ง นับ Frequency และบันทึก Order แล้ว Loop อีกครั้งหาตัวแรกที่ Count=1 รวม O(n)

วิธีที่ 2: ใช้ While Loop + String Replace (O(n²) Time, O(1) Space เพิ่มเติม)

ตัดตัวอักษรทีละตัวออกจาก String เปรียบเทียบความยาว

def first_non_repeating_v2(s: str):
    original = s
    while s:
        ch = s[0]
        s = s.replace(ch, '')  # ลบตัวอักษร ch ทั้งหมด
        if len(s) == len(original) - 1:
            # ถ้าความยาวลดลง 1 เท่านั้น → ch 出現 1 ครั้ง
            return ch
        original = s
    return None

print(first_non_repeating_v2('tutorialspointfordeveloper'))  # u

ผลลัพธ์

u

วิธีที่ 3: ใช้ OrderedDict (Python 3.7+ Dict เรียงลำดับแล้ว)

from collections import OrderedDict

def first_non_repeating_ordered(s: str):
    freq = OrderedDict()
    for c in s:
        freq[c] = freq.get(c, 0) + 1
    
    for char, count in freq.items():
        if count == 1:
            return char
    return None

สรุปเปรียบเทียบ

Stream Version (Real-time)

หากเป็น Stream จริง (ข้อมูลมาทีละตัว) ใช้ Queue + Hash Map:

from collections import deque, defaultdict

class FirstNonRepeatingStream:
    def __init__(self):
        self.queue = deque()
        self.freq = defaultdict(int)
    
    def add(self, char: str):
        self.freq[char] += 1
        self.queue.append(char)
        
        # ลบตัวซ้ำจากหน้า Queue
        while self.queue and self.freq[self.queue[0]] > 1:
            self.queue.popleft()
    
    def get_first_non_repeating(self):
        return self.queue[0] if self.queue else None

# ใช้งาน
stream = FirstNonRepeatingStream()
for c in "tutorialspointfordeveloper":
    stream.add(c)
    print(f"Add '{c}': First non-repeating = {stream.get_first_non_repeating()}")