สมมติว่าเรามีสตริง S ของตัวพิมพ์เล็ก เราจะแบ่งสตริงนี้ออกเป็นส่วนๆ ให้ได้มากที่สุด เพื่อให้แต่ละตัวอักษรปรากฏในส่วนเดียวได้มากที่สุด และสุดท้ายจะแสดงรายการของจำนวนเต็มที่แทนขนาดของชิ้นส่วนเหล่านี้ ดังนั้นหากสตริงเป็นเหมือน “ababcbacadefegdehijhklij” เอาต์พุตจะเป็น [9,7,8] เนื่องจากพาร์ติชั่นคือ “ababcbaca”, “defegde”, “hijhklij” ดังนั้นนี่คือพาร์ทิชันเพื่อให้แต่ละตัวอักษรเกิดขึ้นได้มากที่สุดหนึ่งส่วน พาร์ติชันเช่น "ababcbacadefegde", "hijhklij" ไม่ถูกต้อง เพราะมันแบ่ง S ออกเป็นส่วนน้อย
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดหนึ่งแผนที่เรียกว่า cnt
- สำหรับ i ในช่วง 0 ถึง s, cnt[s[i]] :=i
- j :=0, start :=0 and i :=0 and n :=size of s
- กำหนดหนึ่งอาร์เรย์และ
- ในขณะที่ฉัน
- j :=สูงสุดของ j และ ct[s[i]]
- ถ้า i =j ให้ใส่ i – start + 1 ลงใน ans แล้ว start :=i + 1
- เพิ่ม i ขึ้น 1
ตัวอย่าง(C++)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> partitionLabels(string s) {
map <char, int> cnt;
for(int i = 0; i < s.size(); i++)cnt[s[i]] = i;
int j = 0, start = 0;
int i = 0;
int n = s.size();
vector <int> ans;
while(i < n){
j = max(j, cnt[s[i]]);
if( i == j){
ans.push_back(i-start+ 1);
start = i + 1;
}
i++;
}
return ans;
}
};
main(){
Solution ob;
print_vector(ob.partitionLabels("ababcbacadefegdehijhklij"));
} อินพุต
"ababcbacadefegdehijhklij"
ผลลัพธ์
[9,7,8]
