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 * 10⁴
• 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.