Tìm chuỗi con dài nhất có ít nhất n ký tự lặp lại trong JavaScript

Chúng ta cần viết một hàm JavaScript nhận vào một chuỗi làm đối số đầu tiên và một số nguyên dương n làm đối số thứ hai.

Chuỗi có thể chứa một số ký tự lặp lại. Hàm nên tìm và trả về độ dài của chuỗi con dài nhất từ chuỗi gốc mà trong đó tất cả các ký tự xuất hiện ít nhất n lần.

Ví dụ:

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

const str = 'kdkddj'; const num = 2;

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

const output = 5;

vì chuỗi con dài nhất mong muốn là 'kdkdd'

Ví dụ

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

const str = 'kdkddj'; const num = 2; const longestSubstring = (str = '', num) => {    if(str.length < num){       return 0    };    const map = {}    for(let char of str) {       if(char in map){          map[char] += 1;       }else{          map[char] = 1;       }    }    const minChar = Object.keys(map).reduce((minKey, key) => map[key] <    map[minKey] ? key : minKey)    if(map[minChar] >= num){       return str.length;    };    substrings = str.split(minChar).filter((subs) => subs.length >= num);    if(substrings.length == 0){       return 0;    };    let max = 0;    for(ss of substrings) {       max = Math.max(max, longestSubstring(ss, num))    };    return max; }; console.log(longestSubstring(str, num));

Kết quả

Đầu ra trên console:

5

Giải thích: Divide & conquer: tìm ký tự rarest (min freq). Nếu freq ≥ k → toàn chuỗi valid. Ngược lại, tách chuỗi bởi ký tự đó, đệ quy các phần. LeetCode 395 "Longest Substring with At Least K Repeating Characters".