Tìm ký tự không lặp lại đầu tiên từ stream ký tự (Python)

Bài toán: Tìm ký tự đầu tiên xuất hiện duy nhất 1 lần trong chuỗi/stream.

Phương pháp 1: Dùng dictionary + list (O(n))

def first_non_repeating_char(s):
    char_order = []      # Giữ thứ tự xuất hiện
    counts = {}          # Đếm tần suất
    
    for c in s:
        if c in counts:
            counts[c] += 1
        else:
            counts[c] = 1
            char_order.append(c)
    
    for c in char_order:
        if counts[c] == 1:
            return c
    return None

# Test
print(first_non_repeating_char('PythonforallPythonMustforall'))  # M
print(first_non_repeating_char('tutorialspointfordeveloper'))    # u
print(first_non_repeating_char('AABBCC'))                         # None

Phương pháp 2: Vòng lặp while + replace (O(n²) - chậm)

s = "tutorialspointfordeveloper"
while s:
    ch = s[0]
    s = s.replace(ch, "")
    if len(s) == len(s) - 1:  # Logic lỗi trong code gốc
        # Sửa đúng:
        pass

Code gốc có bug logic so sánh độ dài. Cách đúng:

def first_unique_while(s):
    while s:
        ch = s[0]
        new_s = s.replace(ch, "")
        if len(new_s) == len(s) - 1:  # Chỉ xóa 1 ký tự -> unique
            return ch
        s = new_s
    return None

print(first_unique_while('tutorialspointfordeveloper'))  # u

Phương pháp 3: collections.OrderedDict (Python 3.7+ dict giữ order)

from collections import OrderedDict

def first_unique_ordered(s):
    count = OrderedDict()
    for c in s:
        count[c] = count.get(c, 0) + 1
    for c, cnt in count.items():
        if cnt == 1:
            return c
    return None

Phương pháp 4: Stream processing (online algorithm)

Xử lý từng ký tự một, trả về first non-repeating tại mỗi thời điểm:

from collections import deque, defaultdict

class FirstUniqueStream:
    def __init__(self):
        self.count = defaultdict(int)
        self.queue = deque()
    
    def add(self, char):
        self.count[char] += 1
        self.queue.append(char)
        # Loại bỏ ký tự đã lặp ở đầu queue
        while self.queue and self.count[self.queue[0]] > 1:
            self.queue.popleft()
    
    def get_first_unique(self):
        return self.queue[0] if self.queue else None

# Demo
stream = FirstUniqueStream()
for ch in "tutorialspointfordeveloper":
    stream.add(ch)
    print(f"Add '{ch}': First unique = {stream.get_first_unique()}")

So sánh độ phức tạp

σ = số ký tự distinct