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

题目链接

题目描述

字符串 S 由小写字母组成。
把这个字符串划分为尽可能多的片段,
同一字母最多出现在一个片段中
返回一个表示每个字符串片段的长度的列表。

要求

时间复杂度:O(n)

思路

  • 先遍历一遍 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 Link

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