Partition Labels ใน C++

โจทย์: Partition Labels

ให้สตริง S ประกอบด้วยตัวอักษรพิมพ์เล็ก ต้องแบ่งสตริงออกเป็นจำนวนส่วน (parts) มากที่สุดเท่าที่จะทำได้ โดยที่ แต่ละตัวอักษรต้องปรากฏในได้สูงสุด 1 ส่วนเท่านั้น ส่งคืนลิสต์ของจำนวนเต็มที่แทนขนาดของแต่ละส่วน

ตัวอย่าง: S = "ababcbacadefegdehijhklij"

ผลลัพธ์: [9, 7, 8] เพราะแบ่งได้เป็น "ababcbaca", "defegde", "hijhklij" ตัวอักษรแต่ละตัวอยู่ในส่วนเดียวเท่านั้น

อัลกอริทึม (Greedy + Two Pointers)

1. สร้าง map last_index เก็บ ตำแหน่งสุดท้าย ของแต่ละตัวอักษรในสตริง
2. กำหนด start = 0 (เริ่มต้นของ chunk ปัจจุบัน), end = 0 (สิ้นสุดของ chunk ปัจจุบัน)
3. วนลูป i จาก 0 ถึง n-1:
   • อัปเดต end = max(end, last_index[s[i]]) (ขยายขอบเขต chunk ให้ครอบคลุมตัวอักษรนี้)
   • หาก i == end แสดงว่าจบ chunk แล้ว:
     • บันทึกขนาด chunk: i - start + 1
     • อัปเดต start = i + 1 (เริ่ม chunk ใหม่)
4. ส่งคืนลิสต์ขนาด chunks

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

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<int> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) {
        cout << v[i];
        if (i + 1 < v.size()) cout << ", ";
    }
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> partitionLabels(string s) {
        // ขั้นตอนที่ 1: หาตำแหน่งสุดท้ายของแต่ละตัวอักษร
        unordered_map<char, int> last_index;
        for (int i = 0; i < s.size(); i++)
            last_index[s[i]] = i;

        vector<int> ans;
        int start = 0, end = 0;

        // ขั้นตอนที่ 2: Greedy partitioning
        for (int i = 0; i < s.size(); i++) {
            end = max(end, last_index[s[i]]);
            if (i == end) {
                ans.push_back(i - start + 1);
                start = i + 1;
            }
        }
        return ans;
    }
};

int main() {
    Solution ob;
    print_vector(ob.partitionLabels("ababcbacadefegdehijhklij"));
    return 0;
}

Input

"ababcbacadefegdehijhklij"

Output

[9, 7, 8]

ความซับซ้อน (Complexity)

• เวลา: O(n) - วนลูปผ่านสตริง 2 รอบ
• พื้นที่: O(1) - map เก็บได้สูงสุด 26 ตัวอักษร (คงที่)