Chia chuỗi thành nhiều phần tối đa trong JavaScript

Vấn đề

Chúng ta cần viết một hàm JavaScript nhận vào một chuỗi str làm đối số duy nhất. Mục đích là phân vùng chuỗi này thành nhiều phần nhất có thể sao cho mỗi chữ cái chỉ xuất hiện trong tối đa một phần, và trả về mảng số nguyên đại diện cho kích thước các phần này.

Ví dụ, nếu đầu vào là:

Đầu vào

const str = "ababcbacadefegdehijhklij";

Đầu ra

const output = [9, 7, 8];

Giải thích

Phân vùng là "ababcbaca", "defegde", "hijhklij". Mỗi chữ cái chỉ xuất hiện trong một phần. Phân vùng như "ababcbacadefegde", "hijhklij" sai vì chia ít phần hơn.

Ví dụ

Dưới đây là mã thực hiện:

const str = "ababcbacadefegdehijhklij";
const splitStrings = (str = '') => {
  const res = [];
  const map = {};
  for (let i = 0; i < str.length; i++) {
    map[str[i]] = i;
  }
  let start = 0;
  while (start <= str.length - 1) {
    let end = map[str[start]];
    for (let i = start + 1; i < end; i++) {
      const currentEnd = map[str[i]];
      if (currentEnd > end) {
        end = currentEnd;
      }
    }
    res.push(end - start + 1);
    start = end + 1;
  }
  return res;
};
console.log(splitStrings(str));

Kết quả

[9, 7, 8]