Partition Labels trong C++

Cho chuỗi S chỉ chứa chữ thường. Phân chia chuỗi 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. Trả về mảng kích thước các phần.

Ví dụ: "ababcbacadefegdehijhklij" → [9,7,8] vì phân chia: "ababcbaca", "defegde", "hijhklij".

Giải thuật

• Tạo map cnt lưu vị trí cuối cùng của mỗi ký tự.
• Duyệt chuỗi, cập nhật j = max(j, cnt[s[i]]).
• Khi i == j, cắt đoạn, lưu độ dài i - start + 1, cập nhật start = i + 1.

Ví dụ code

#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] << (i+1
Input
"ababcbacadefegdehijhklij"
Output
[9,7,8]