Tìm chuỗi con cửa sổ nhỏ nhất (Min Window Substring) trong JavaScript

Chúng ta cần viết một hàm JavaScript nhận vào hai chuỗi, gọi chúng là str1 và str2.

Kích thước của str1 đảm bảo lớn hơn str2. Chúng ta cần tìm chuỗi con nhỏ nhất trong str1 chứa tất cả các ký tự có trong str2.

Ví dụ:

Nếu chuỗi đầu vào là:

const str1 = 'abcdefgh'; const str2 = 'gedcf';

Thì đầu ra nên là:

const output = 'cdefg';

vì đây là chuỗi con liên tiếp nhỏ nhất của str1 chứa tất cả ký tự của str2.

Ví dụ

Dưới đây là mã nguồn:

const str1 = 'abcdefgh'; const str2 = 'gedcf'; const subIncludesAll = (str, str2) => {    for (let i = 0; i < str.length; i++) {       if (str2.indexOf(str[i]) !== -1) {          str2 = str2.replace(str[i], '');       };    };    return (str2.length === 0); }; const minWindow = (str1 = '', str2 = '') => {    let shortestString = null;    for (let i = 0; i < str1.length; i++) {       for (let j = i; j < str1.length; j++) {          let testString = str1.substr(i, j-i+1);          if (subIncludesAll(testString, str2)) {             if (shortestString === null || testString.length < shortestString.length) {                shortestString = testString;             }          }       }    }    return shortestString; }; console.log(minWindow(str1, str2));

Kết quả

Đầu ra trên console:

cdefg

Lưu ý: Giải pháp vét cạn O(n³) chỉ phù hợp chuỗi rất ngắn. Bài toán kinh điển "Minimum Window Substring" (LeetCode 76) giải O(n) bằng sliding window + hash map đếm tần suất.