# Leetcode-763-划分字母区间(Leetcode-763-divide letter interval)-其他

## Leetcode-763-划分字母区间(Leetcode-763-divide letter interval)

### 思路

• 先遍历一遍 s ，用 map 记录每一个字母出现的区间。
问题就转化成了对区间的合并操作。
• 再遍历一遍 s ，一边遍历，一边处理当前字符所出现的区间。
若区间有重叠，直接合并，
若无重叠，更新答案。

### C++代码

``````class Solution {
public:
vector<int> partitionLabels(string s) {
vector<int> ans;
unordered_map<char, pair<int, int>> mp;
int len  = s.length();
for (int i = 0; i < len; i++) {
if (mp.count(s[i]) == 0)
mp[s[i]].first = mp[s[i]].second = i;
else
mp[s[i]].second = i;
}

int L= 0, R = 0;
for (int i = 0; i < len; i++) {
if (mp[s[i]].first > R) {
ans.push_back(R-L+1);
L = i;
R = mp[s[i]].second;
} else if (mp[s[i]].second > R) {
R = mp[s[i]].second;
}
}
ans.push_back(R-L+1);
return ans;
}
};
``````
————————

### Title Description

The string s consists of lowercase letters.
Divide the string into < strong > as many < / strong > segments as possible,
< strong > the same letter can appear in one segment at most < / strong >.
Returns a list representing the length of each string fragment.

### requirement

Time complexity: n

### thinking

• First traverse s, and record the interval of each letter with map.
The problem is transformed into the merging operation of intervals.
• Traverse s again, and process the interval of the current character while traversing.
If the intervals overlap, merge them directly,
If there is no overlap, update the answer.

### C + + code

``````class Solution {
public:
vector<int> partitionLabels(string s) {
vector<int> ans;
unordered_map<char, pair<int, int>> mp;
int len  = s.length();
for (int i = 0; i < len; i++) {
if (mp.count(s[i]) == 0)
mp[s[i]].first = mp[s[i]].second = i;
else
mp[s[i]].second = i;
}

int L= 0, R = 0;
for (int i = 0; i < len; i++) {
if (mp[s[i]].first > R) {
ans.push_back(R-L+1);
L = i;
R = mp[s[i]].second;
} else if (mp[s[i]].second > R) {
R = mp[s[i]].second;
}
}
ans.push_back(R-L+1);
return ans;
}
};
``````