Kiểm tra chuỗi có tất cả ký tự duy nhất (Unique characters) trong C#

Bài toán: Cho một chuỗi, xác định xem có chứa tất cả ký tự duy nhất (không có ký tự nào lặp lại) hay không.

Giải pháp 1: Dùng HashSet (Khuyên dùng - O(n))

using System;
using System.Collections.Generic;

class Program
{
    static bool HasAllUniqueChars(string input)
    {
        if (string.IsNullOrEmpty(input)) return true;
        
        var seen = new HashSet<char>();
        foreach (char c in input)
        {
            if (seen.Contains(c))
                return false; // Trùng lặp
            seen.Add(c);
        }
        return true;
    }
    
    static void Main()
    {
        string[] tests = { "abcdef", "hello", "", "a", "abcdea" };
        foreach (var s in tests)
            Console.WriteLine($"\"{s}\" -> {HasAllUniqueChars(s)}");
    }
}

Giải pháp 2: Dùng mảng Boolean (ASCII - O(n), không gian O(1))

Nếu chuỗi chỉ chứa ASCII (128 ký tự) hoặc Extended ASCII (256 ký tự):

static bool HasAllUniqueCharsAscii(string input)
{
    if (input.Length > 128) return false; // Đỉnh pigeonhole principle
    
    bool[] charSet = new bool[128]; // ASCII
    foreach (char c in input)
    {
        int val = c;
        if (charSet[val]) return false;
        charSet[val] = true;
    }
    return true;
}

Giải pháp 3: Bit Vector (Chỉ a-z, A-Z - O(n), không gian O(1))

Dùng một int (32 bit) làm bit mask cho 26 chữ cái:

static bool HasAllUniqueCharsBitVector(string input)
{
    int checker = 0;
    foreach (char c in input)
    {
        // Chỉ xử lý a-z (bỏ qua case hoặc chuẩn hóa)
        int bitIndex = char.ToLower(c) - 'a';
        if (bitIndex < 0 || bitIndex > 25) continue; // Bỏ qua non-alpha
        
        if ((checker & (1 << bitIndex)) > 0)
            return false;
        checker |= (1 << bitIndex);
    }
    return true;
}

Giải pháp 4: Sắp xếp rồi so sánh liền kề (O(n log n), không gian O(1))

static bool HasAllUniqueCharsSort(string input)
{
    char[] chars = input.ToCharArray();
    Array.Sort(chars);
    for (int i = 1; i < chars.Length; i++)
        if (chars[i] == chars[i - 1])
            return false;
    return true;
}

So sánh

Khuyến nghị: Dùng HashSet<char> cho code thực tế (hỗ trợ Unicode, đọc hiểu dễ). Dùng Bit Vector cho thuật toán phỏng vấn/đề bài giới hạn a-z.