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

Đăng nhận xét

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

Biến Trong PHP

Khái niệm về biến trong PHP là kiến thức nền tảng trong lập trình PHP mà hầu như lập trình viên nào cũng phải học đầu tiên. Trong bài này chúng ta sẽ đi tìm hiểu khái niệm thế nào là biến. I. Biến trong php để làm gì Bạn còn nhớ môn Đại Số ở  Trường Không ? Dạng như , x = 1 , y = 2 , z =3 Bạn còn nhớ với mỗi từ ta có thể gán 1 giá trị (vd : x = 2 , y = 123 , z = 52 v.v ) và bạn sẽ dùng mấy thông tin đó để tính 1 giá trị nào đó của d chẳng hạn . Tất cả những cái trên được gọi là Biến PHP , và biến được dùng để giữ 1 giá trị nhất định (x=2) hoặc là các bài toán như ( d = a+b+c ) trong đó a,b,c là các hằng số có giá trị bất kỳ ( vd : a = 1 , b = 2 , c = 3 thì d = a + b + c = 6 ) Ví dụ: <!DOCTYPE html> <html> <body> <?php //Đây là chú thích 1 dòng /* Đây là chú thích Nhiều Dòng */ ?> </body> </html> Biến PHP Với đại số, các biến PHP được sử dụng để giữ các giá trị hoặc biểu thức. Một biến có thể có một tên ngắn, như x, hoặc một cái tên dài ...
Đăng nhận xét
Đọc thêm

Biến Trong PHP

Khái niệm về biến trong PHP là kiến thức nền tảng trong lập trình PHP mà hầu như lập trình viên nào cũng phải học đầu tiên. Trong bài này chúng ta sẽ đi tìm hiểu khái niệm thế nào là biến. I. Biến trong php để làm gì Bạn còn nhớ môn Đại Số ở  Trường Không ? Dạng như , x = 1 , y = 2 , z =3 Bạn còn nhớ với mỗi từ ta có thể gán 1 giá trị (vd : x = 2 , y = 123 , z = 52 v.v ) và bạn sẽ dùng mấy thông tin đó để tính 1 giá trị nào đó của d chẳng hạn . Tất cả những cái trên được gọi là Biến PHP , và biến được dùng để giữ 1 giá trị nhất định (x=2) hoặc là các bài toán như ( d = a+b+c ) trong đó a,b,c là các hằng số có giá trị bất kỳ ( vd : a = 1 , b = 2 , c = 3 thì d = a + b + c = 6 ) Ví dụ: <!DOCTYPE html> <html> <body> <?php //Đây là chú thích 1 dòng /* Đây là chú thích Nhiều Dòng */ ?> </body> </html> Biến PHP Với đại số, các biến PHP được sử dụng để giữ các giá trị hoặc biểu thức. Một biến có thể có một tên ngắn, như x, hoặc một cái tên dài ...
Đăng nhận xét
Đọc thêm

Chuỗi Trong PHP

I. String trong php là gì Chuỗi biến được sử dụng sử dụng cho các giá trị có chứa ký tự . Trong chương trình này, chúng ta sẽ nhìn vào chức năng phổ biến nhất được sử dụng để thao tác các chuỗi trong PHP. Sau khi chúng tôi tạo ra một chuỗi, chúng ta có thể thao tác nó . Một chuỗi có thể được sử dụng trực tiếp trong một hàm hoặc nó có thể được lưu trữ trong một biến . Dưới đây, các tập lệnh PHP gán văn bản “Hello World” vào một chuỗi biến gọi là $ txt: <?php $txt="Hello World"; echo $txt; ?> Khi thực thi code trên thì sẽ ra kết quả trả về là “Hello World” Nào , bây giờ chúng ta thử 1 số chức năng và các chức năng khác nhau để xử lý 1 chuỗi <?php $txt1="Hello World!"; $txt2="What a nice day!"; echo $txt1 . " " . $txt2; ?> Kết quả trả về sẽ là Hello World ! What a nice day! Nếu chúng ta nhìn vào đoạn mã trên, bạn thấy rằng chúng ta sử dụng toán tử nối hai lần. Điều này là bởi vì chúng tôi đã để chèn một chuỗi thứ ba, để phân c...
Đăng nhận xét
Đọc thêm