Chuyển đến nội dung chính

Bài 3 Leetcode: Longest Substring Without Repeating Characters

Đề bài:

Cho một chuỗi s, tìm độ dài của chuỗi con dài nhất mà không chứa các ký tự lặp lại.

Ví dụ 1: 

Input: s = "abcabcbb"
Output: 3
Giải thích: Đáp án là "abc", với độ dài là 3.

Ví dụ 2:

Input: s = "bbbbb"
Output: 1
Giải thích: Đáp án là "b", với độ dài là 1.

Ví dụ 3:

Input: s = "pwwkew"
Output: 3
Giải thích: Đáp án là "wke", với độ dài là 3.
Lưu ý rằng đáp án phải là một chuỗi con (substring), "pwke" là một dãy con (subsequence) và không phải là một chuỗi con.

Ràng buộc:

  • 0 <= độ dài của chuỗi s <= 5 * 104
  • s chỉ gồm các chữ cái tiếng Anh, chữ số, ký tự đặc biệt và khoảng trắng.

Cách 1: Sliding window

Giải thích thuật toán bằng C++

class Solution {
 public:
  int lengthOfLongestSubstring(string s) {
    int ans = 0;
    vector<int> count(128);

    for (int l = 0, r = 0; r < s.length(); ++r) {
      ++count[s[r]];
      while (count[s[r]] > 1)
        --count[s[l++]];
      ans = max(ans, r - l + 1);
    }

    return ans;
  }
};

Đoạn mã trên triển khai thuật toán để tìm độ dài của chuỗi con dài nhất mà không chứa các ký tự lặp lại trong một chuỗi cho trước. Dưới đây là giải thích chi tiết về cách thuật toán hoạt động:

1. Khởi tạo biến ans bằng 0, đại diện cho độ dài của chuỗi con dài nhất tìm được.
2. Khởi tạo một vector count với kích thước 128 (tương ứng với bảng mã ASCII), mỗi phần tử trong vector đại diện cho số lần xuất hiện của một ký tự trong chuỗi.
3. Bắt đầu một vòng lặp từ l = 0 đến r = 0 (ban đầu cả hai chỉ về đầu chuỗi).
4. Trong mỗi vòng lặp, tăng giá trị count[s[r]] lên 1, đồng thời di chuyển r sang phần tử tiếp theo trong chuỗi.
5. Kiểm tra nếu count[s[r]] > 1, tức là ký tự tại vị trí r đã xuất hiện trước đó trong chuỗi con hiện tại. Trong trường hợp này, ta cần di chuyển l (đầu chuỗi) sang phải cho đến khi không còn ký tự lặp lại, bằng cách giảm giá trị count[s[l]] đi 1.
6. Tại mỗi vòng lặp, tính toán độ dài của chuỗi con hiện tại là r – l + 1 và cập nhật giá trị ans nếu độ dài này lớn hơn giá trị hiện tại của ans.
7. Khi vòng lặp kết thúc, trả về giá trị ans là độ dài của chuỗi con dài nhất không chứa các ký tự lặp lại.

Thuật toán này sử dụng kỹ thuật cửa sổ trượt (sliding window) để xác định chuỗi con dài nhất mà không chứa ký tự lặp lại. Khi gặp một ký tự đã xuất hiện trước đó, ta di chuyển đầu chuỗi (l) sang phải cho đến khi không còn ký tự lặp lại, đồng thời cập nhật độ dài của chuỗi con hiện tại.

Giải thích thuật toán bằng Java

class Solution {
  public int lengthOfLongestSubstring(String s) {
    int ans = 0;
    int[] count = new int[128];

    for (int l = 0, r = 0; r < s.length(); ++r) {
      ++count[s.charAt(r)];
      while (count[s.charAt(r)] > 1)
        --count[s.charAt(l++)];
      ans = Math.max(ans, r - l + 1);
    }

    return ans;
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def lengthOfLongestSubstring(self, s: str) -> int:
    ans = 0
    count = collections.Counter()

    l = 0
    for r, c in enumerate(s):
      count[c] += 1
      while count[c] > 1:
        count[s[l]] -= 1
        l += 1
      ans = max(ans, r - l + 1)

    return ans

 

Cách 2: Last seen

Giải thích thuật toán bằng C++

class Solution {
 public:
  int lengthOfLongestSubstring(string s) {
    int ans = 0;
    // The substring s[j + 1..i] has no repeating characters.
    int j = -1;
    // lastSeen[c] := the index of the last time c appeared.
    vector<int> lastSeen(128, -1);

    for (int i = 0; i < s.length(); ++i) {
      // Update j to lastSeen[s[i]], so the window must start from j + 1.
      j = max(j, lastSeen[s[i]]);
      ans = max(ans, i - j);
      lastSeen[s[i]] = i;
    }

    return ans;
  }
};

Đoạn mã trên là một phương thức trong lớp `Solution` được viết bằng ngôn ngữ C++ để tìm độ dài của chuỗi con dài nhất mà không chứa các ký tự lặp lại.

Phương thức `lengthOfLongestSubstring` nhận đầu vào là một chuỗi `s` và trả về một số nguyên đại diện cho độ dài của chuỗi con dài nhất mà không chứa các ký tự lặp lại.

Ban đầu, biến `ans` được khởi tạo với giá trị 0 để lưu trữ độ dài của chuỗi con dài nhất tìm được.

Biến `j` được khởi tạo với giá trị -1, đại diện cho chỉ số cuối cùng của chuỗi con không chứa ký tự lặp lại.

Một vector `lastSeen` được khởi tạo với kích thước 128 và các phần tử ban đầu được đặt là -1. Vector này được sử dụng để lưu vị trí xuất hiện cuối cùng của mỗi ký tự trong chuỗi.

Vòng lặp for được sử dụng để duyệt qua từng ký tự trong chuỗi `s`.

Trong mỗi vòng lặp, biến `j` được cập nhật bằng giá trị lớn nhất giữa `j` và `lastSeen[s[i]]`. Điều này đảm bảo rằng cửa sổ (window) của chuỗi con không chứa ký tự lặp lại sẽ bắt đầu từ `j + 1`.

Biến `ans` được cập nhật bằng giá trị lớn nhất giữa `ans` và `i – j`. Điều này đảm bảo rằng `ans` sẽ lưu trữ độ dài của chuỗi con dài nhất tìm được.

Cuối cùng, `lastSeen[s[i]]` được cập nhật với giá trị `i`, đại diện cho vị trí xuất hiện cuối cùng của ký tự `s[i]` trong chuỗi.

Sau khi vòng lặp kết thúc, `ans` sẽ chứa độ dài của chuỗi con dài nhất không chứa ký tự lặp lại và được trả về.

Giải thích thuật toán bằng Java

class Solution {
  public int lengthOfLongestSubstring(String s) {
    int ans = 0;
    // The substring s[j + 1..i] has no repeating characters.
    int j = -1;
    // lastSeen[c] := the index of the last time c appeared
    int[] lastSeen = new int[128];
    Arrays.fill(lastSeen, -1);

    for (int i = 0; i < s.length(); ++i) {
      // Update j to lastSeen[s.charAt(i)], so the window must start from j + 1.
      j = Math.max(j, lastSeen[s.charAt(i)]);
      ans = Math.max(ans, i - j);
      lastSeen[s.charAt(i)] = i;
    }

    return ans;
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def lengthOfLongestSubstring(self, s: str) -> int:
    ans = 0
    # The substring s[j + 1..i] has no repeating characters.
    j = -1
    # lastSeen[c] := the index of the last time c appeared
    lastSeen = {}

    for i, c in enumerate(s):
      # Update j to lastSeen[c], so the window must start from j + 1.
      j = max(j, lastSeen.get(c, -1))
      ans = max(ans, i - j)
      lastSeen[c] = i

    return ans

The post Bài 3 Leetcode: Longest Substring Without Repeating Characters first appeared on Techacademy.



Nhận xét

Bài đăng phổ biến từ blog này

Học Lập Trình Android Ở Đâu TpHCM, Hà Nội, Đà Nẵng ? Tốt Nhất, Uy Tín Nhất

Học lập trình Android là một trong những khóa học lập trình được nhiều bạn trẻ tìm kiếm nhất hiện nay bởi mực lương hấp dẫn và ổn định của một lập trình viên android. Đối với các bạn trẻ bắt đầu theo học android việc suy nghĩ học lập trình android ở đâu luôn là vấn đề được rất nhiều quan tâm. Để biết được câu trả lời khách quan nhất về học lập trình android ở đâu tại TpHCM, Hà Nội, Đà Nẵng? Mời bạn tham khảo ngay ý kiến từ Techacademy đưa ra dưới đây nhé! I. Học lập trình android ở đâu tốt nhất Hà Nôi, TpHCM, Đà Nẵng Dưới đây là danh sách các trung tâm đào tạo lập trình android hàng đầu Việt Nam hiện nay. 1, Techacademy Sử dụng phương pháp giảng dạy lập trình android được hiệu quả, giúp học viện hiểu bài và áp dụng thục hành ngay trong thực tế. Đây là phương pháp dạy lập trình android hiệu quả nhất hiện nay, giúp học viên xây dựng sự tự tin khi thực hành. Techacademy là trung tâm đào tạo lập trình android hàng đầu tại Việt Nam, được thành lập với đội ngũ giảng viên, chuyên gia lậ...

Phím Tắt Eclipse Thông Dụng Và Tiện Lợi Nhất ! Đọc Ngay Nếu Bạn Vẫn Đang Dùng Chuột

Việc sử dụng các thao tác click chuột nhiều lần trong Eclipse khiến các coder nhàm chán và tốn thời gian, hãy cải tạo nó bằng các phím tắt trong Eclipse. Dưới đây là danh sách một số những phím tắt thông dụng bạn nên biết. phím tắt eclipse (1) Đầu tiên hãy sử dụng phím tắt Ctrl + Shift + L để hiển thị danh sách các phím tắt trong Eclipse. phím tắt eclipse (2) Danh sách tất cả những phím tắt trong Eclipse bạn có thể áp dụng, được chia thành 12 mục khác nhau tùy thuộc vào tác dụng của phím tắt: 1. Quản lý tập tin và dự án Ctrl + N Tạo dự án mới bằng Wizard Ctrl + Alt + N Tạo dự án , tập tin, lớp, vv Alt + F Mở dự án, tệp, v.v. Ctrl + Shift + R Mở Resource (tệp, thư mục hoặc dự án) Alt + Enter Hiển thị và truy cập các thuộc tính tệp Ctrl + S Save tập tin hiện tại Ctrl + Shift + S Save tất cả các tập tin Ctrl + W Đóng tệp hiện tại Ctrl + Shift + W Đóng tất cả các tệp F5 Làm mới nội dung của phần tử đã chọn bằng hệ thống tệp cục bộ 2. Cửa sổ trình chỉnh sửa F1...

Hướng Dẫn Cài Đặt Python Trên Máy Tính?

Python là một ngôn ngữ lập trình phổ biến và được sử dụng rộng rãi trong lĩnh vực phát triển phần mềm và khoa học dữ liệu. Để bắt đầu sử dụng Python trên máy tính của bạn, bạn cần cài đặt nó. Trong bài viết này, chúng tôi sẽ hướng dẫn bạn cách cài đặt Python trên máy tính một cách dễ dàng. I. Cài Đặt Python Trên Vscode Python là một ngôn ngữ lập trình phổ biến và VS Code là một trình soạn thảo mã nguồn được ưa chuộng. Kết hợp cả hai, bạn có thể tận dụng lợi ích của cả hai công cụ để phát triển ứng dụng Python một cách hiệu quả. Trong bài viết này, chúng tôi sẽ hướng dẫn cách cài đặt Python trên VS Code. Bước 1: Cài đặt VS Code Trước khi bắt đầu, bạn cần cài đặt VS Code trên máy tính của mình. Truy cập trang web vscode.com, tải xuống phiên bản phù hợp với hệ điều hành của bạn và làm theo hướng dẫn trên màn hình để hoàn tất quá trình cài đặt. Bước 2: Cài đặt Extension Python cho VS Code Sau khi cài đặt VS Code, bạn cần cài đặt extension Python để hỗ trợ phát triển ứng dụng Python t...