การแบ่งสตริงเป็นส่วนมากที่สุดใน JavaScript

ปัญหา

เราต้องเขียนฟังก์ชัน JavaScript ที่รับสตริง str เป็นอาร์กิวเมนต์เดียว

วัตถุประสงค์ของฟังก์ชันคือแบ่งพาร์ติชันสตริงนี้เป็นส่วนมากที่สุดเท่าที่จะทำได้ เพื่อให้แต่ละตัวอักษรปรากฏในสูงสุดหนึ่งส่วน และคืนค่าอาร์เรย์ของจำนวนเต็มที่แทนขนาดของส่วนเหล่านี้

ตัวอย่างเช่น หากอินพุตคือ

อินพุต

const str = "ababcbacadefegdehijhklij";

เอาต์พุต

const output = [9, 7, 8];

คำอธิบายเอาต์พุต

พาร์ติชันคือ "ababcbaca", "defegde", "hijhklij" นี่คือพาร์ติชันที่ทำให้แต่ละตัวอักษรปรากฏในสูงสุดหนึ่งส่วน พาร์ติชันแบบ "ababcbacadefegde", "hijhklij" ไม่ถูกต้อง เพราะมันแบ่งสตริงเป็นส่วนน้อยกว่า

ตัวอย่างโค้ด

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));

ผลลัพธ์

[ 9, 7, 8 ]