1. Đảo ngược chuỗi ký tự

Mô tả bài toán: Viết một hàm để đảo ngược một chuỗi ký tự. Chuỗi đầu vào được cho dưới dạng một mảng ký tự `s`. Bạn phải sửa đổi mảng đầu vào tại chỗ, không được cấp phát thêm không gian cho một mảng khác và sử dụng không gian phụ trợ O(1).

Phương pháp giải: Sử dụng kỹ thuật hai con trỏ, một con trỏ bắt đầu từ đầu chuỗi và một con trỏ bắt đầu từ cuối chuỗi. Đổi chỗ các ký tự tại hai vị trí này, sau đó di chuyển hai con trỏ về phía trung tâm cho đến khi chúng gặp nhau.

from typing import List

class ChuoiDaoNguoc:
    def daoNguoc(self, s: List[str]) -> None:
        """
        Đảo ngược chuỗi ký tự tại chỗ.
        """
        i = 0
        j = len(s) - 1
        
        while i < j:
            # Đổi chỗ ký tự tại vị trí i và j
            s[i], s[j] = s[j], s[i]
            i += 1
            j -= 1

# Ví dụ sử dụng
if __name__ == '__main__':
    solution = ChuoiDaoNguoc()
    chuoi = list("hello")
    print("Trước:", chuoi)
    solution.daoNguoc(chuoi)
    print("Sau:", chuoi)

2. Đảo ngược chuỗi ký tự II

Mô tả bài toán: Cho một chuỗi `s` và một số nguyên `k`. Mỗi khi đếm được `2k` ký tự, hãy đảo ngược `k` ký tự đầu tiên trong `2k` ký tự đó. Nếu số ký tự còn lại ít hơn `k`, hãy đảo ngược tất cả các ký tự còn lại. Nếu số ký tự còn lại ít hơn `2k` nhưng lớn hơn hoặc bằng `k`, hãy đảo ngược `k` ký tự đầu tiên, các ký tự còn lại giữ nguyên.

Phương pháp giải: Duyệt qua chuỗi với bước nhảy là `2k`. Với mỗi đoạn con có độ dài `k`, thực hiện đảo ngược đoạn đó.

class ChuoiDaoNguocII:
    def daoNguocDoan(self, doan: List[str]) -> List[str]:
        """
        Đảo ngược một đoạn con của chuỗi.
        """
        dau = 0
        cuoi = len(doan) - 1
        
        while dau < cuoi:
            doan[dau], doan[cuoi] = doan[cuoi], doan[dau]
            dau += 1
            cuoi -= 1
            
        return doan

    def daoNguocChuoiII(self, s: str, k: int) -> str:
        """
        Đảo ngược chuỗi theo quy tắc đã cho.
        """
        chuoi_list = list(s)
        i = 0
        n = len(s)
        
        while i < n:
            # Xác định vị trí kết thúc của đoạn cần đảo ngược
            cuoi_doan = min(i + k, n)
            # Đảo ngược đoạn con từ i đến cuoi_doan
            chuoi_list[i:cuoi_doan] = self.daoNguocDoan(chuoi_list[i:cuoi_doan])
            # Nhảy đến đoạn tiếp theo
            i += 2 * k
            
        return "".join(chuoi_list)

# Ví dụ sử dụng
if __name__ == '__main__':
    solution = ChuoiDaoNguocII()
    chuoi = 'abcdefg'
    k = 2
    print(solution.daoNguocChuoiII(chuoi, k))

3. Thay thế khoảng trắng

Mô tả bài toán: Viết một hàm để thay thế mỗi khoảng trắng trong chuỗi `s` bằng chuỗi `"%20"`.

Phương pháp giải: Duyệt qua từng ký tự của chuỗi. Nếu là khoảng trắng, thêm chuỗi `"%20"` vào kết quả. Nếu không, thêm ký tự đó vào kết quả.

class ThayTheKhoangTrang:
    def thayTheKhoangTrang(self, s: str) -> str:
        """
        Thay thế tất cả các khoảng trắng trong chuỗi bằng "%20".
        """
        ket_qua = []
        for ky_tu in s:
            if ky_tu == ' ':
                ket_qua.append('%20')
            else:
                ket_qua.append(ky_tu)
        return "".join(ket_qua)

# Ví dụ sử dụng
if __name__ == '__main__':
    solution = ThayTheKhoangTrang()
    chuoi = 'We Are Happy'
    print(solution.thayTheKhoangTrang(chuoi))

4. Đảo ngược từng từ trong chuỗi

Mô tả bài toán: Cho một chuỗi, hãy đảo ngược từng từ trong chuỗi đó.

Phương pháp giải: Đầu tiên, đảo ngược toàn bộ chuỗi. Sau đó, duyệt qua chuỗi đã đảo ngược để xác định và đảo ngược lại từng từ.

class DaoNguocTu:
    def daoNguocDoan(self, doan: List[str]) -> List[str]:
        """
        Đảo ngược một đoạn con của chuỗi.
        """
        dau = 0
        cuoi = len(doan) - 1
        
        while dau < cuoi:
            doan[dau], doan[cuoi] = doan[cuoi], doan[dau]
            dau += 1
            cuoi -= 1
            
        return doan

    def daoNguocTu(self, s: str) -> str:
        """
        Đảo ngược từng từ trong chuỗi.
        """
        # Chuyển chuỗi thành list ký tự để dễ thao tác
        chuoi_list = list(s)
        # Đảo ngược toàn bộ chuỗi
        chuoi_list = self.daoNguocDoan(chuoi_list)
        
        ket_qua = []
        i = 0
        n = len(chuoi_list)
        
        while i < n:
            # Bỏ qua các khoảng trắng
            while i < n and chuoi_list[i] == ' ':
                i += 1
            
            if i >= n:
                break
                
            # Bắt đầu của một từ
            start = i
            # Tìm đến cuối của từ
            while i < n and chuoi_list[i] != ' ':
                i += 1
            
            # Lấy đoạn ký tự của từ và đảo ngược nó
            tu = chuoi_list[start:i]
            tu_dao_nguoc = self.daoNguocDoan(tu)
            ket_qua.append("".join(tu_dao_nguoc))
            
        return " ".join(ket_qua)

# Ví dụ sử dụng
if __name__ == '__main__':
    solution = DaoNguocTu()
    chuoi = 'the sky is blue'
    print(solution.daoNguocTu(chuoi))

5. Xoay chuỗi sang trái

Mô tả bài toán: Phép xoay trái chuỗi là di chuyển một số ký tự đầu tiên của chuỗi đến cuối chuỗi. Hãy viết một hàm để thực hiện phép xoay trái này. Ví dụ, với chuỗi "abcdefg" và số 2, hàm sẽ trả về "cdefgab".

Phương pháp giải: Tách chuỗi thành hai phần: phần đầu có độ dài `n` và phần còn lại. Sau đó, nối phần sau với phần đầu để tạo thành chuỗi kết quả.

class XoayChuoiTrai:
    def xoayChuoiTrai(self, s: str, n: int) -> str:
        """
        Xoay chuỗi sang trái.
        """
        if not s:
            return ""
            
        do_dai = len(s)
        # Xử lý trường hợp n lớn hơn độ dài chuỗi
        n = n % do_dai
        
        # Phần chuỗi sau khi cắt
        phan_duoi = s[n:]
        # Phần chuỗi bị cắt
        phan_dau = s[:n]
        
        return phan_duoi + phan_dau

# Ví dụ sử dụng
if __name__ == '__main__':
    solution = XoayChuoiTrai()
    chuoi = "aab"
    n = 10
    print(solution.xoayChuoiTrai(chuoi, n))