763.划分字母区间

class Solution {
public:
    vector<int> partitionLabels(string S) {
        int hash[27] = {0}; // i为字符，hash[i]为字符出现的最后位置
        for (int i = 0; i < S.size(); i++) { // 统计每一个字符最后出现的位置
            hash[S[i] - 'a'] = i;
        }
        vector<int> result;
        int left = 0;
        int right = 0;
        for (int i = 0; i < S.size(); i++) {
            right = max(right, hash[S[i] - 'a']); // 找到字符出现的最远边界
            if (i == right) {
                result.push_back(right - left + 1);
                left = i + 1;
            }
        }
        return result;
    }
};

class Solution {
public:
    static bool cmp(vector<int> &a, vector<int> &b) {
        return a[0] < b[0];
    }
    // 记录每个字母出现的区间
    vector<vector<int>> countLabels(string s) {
        vector<vector<int>> hash(26, vector<int>(2, INT_MIN));
        vector<vector<int>> hash_filter;
        for (int i = 0; i < s.size(); ++i) {
            if (hash[s[i] - 'a'][0] == INT_MIN) {
                hash[s[i] - 'a'][0] = i;
            }
            hash[s[i] - 'a'][1] = i;
        }
        // 去除字符串中未出现的字母所占用区间
        for (int i = 0; i < hash.size(); ++i) {
            if (hash[i][0] != INT_MIN) {
                hash_filter.push_back(hash[i]);
            }
        }
        return hash_filter;
    }
    vector<int> partitionLabels(string s) {
        vector<int> res;
        // 这一步得到的 hash 即为无重叠区间题意中的输入样例格式：区间列表
        // 只不过现在我们要求的是区间分割点
        vector<vector<int>> hash = countLabels(s);
        // 按照左边界从小到大排序
        sort(hash.begin(), hash.end(), cmp);
        // 记录最大右边界
        int rightBoard = hash[0][1];
        int leftBoard = 0;
        for (int i = 1; i < hash.size(); ++i) {
            // 由于字符串一定能分割，因此,
            // 一旦下一区间左边界大于当前右边界，即可认为出现分割点
            if (hash[i][0] > rightBoard) {
                res.push_back(rightBoard - leftBoard + 1);
                leftBoard = hash[i][0];
            }
            rightBoard = max(rightBoard, hash[i][1]);
        }
        // 最右端
        res.push_back(rightBoard - leftBoard + 1);
        return res;
    }
};

class Solution {
    public List<Integer> partitionLabels(String S) {
        List<Integer> list = new LinkedList<>();
        int[] edge = new int[26];
        char[] chars = S.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            edge[chars[i] - 'a'] = i;
        }
        int idx = 0;
        int last = -1;
        for (int i = 0; i < chars.length; i++) {
            idx = Math.max(idx,edge[chars[i] - 'a']);
            if (i == idx) {
                list.add(i - last);
                last = i;
            }
        }
        return list;
    }
}

class Solution{
    /*解法二： 上述c++补充思路的Java代码实现*/
    
    public  int[][] findPartitions(String s) {
        List<Integer> temp = new ArrayList<>();
        int[][] hash = new int[26][2];//26个字母2列 表示该字母对应的区间

        for (int i = 0; i < s.length(); i++) {
            //更新字符c对应的位置i
            char c = s.charAt(i);
            if (hash[c - 'a'][0] == 0) hash[c - 'a'][0] = i;

            hash[c - 'a'][1] = i;

            //第一个元素区别对待一下
            hash[s.charAt(0) - 'a'][0] = 0;
        }


        List<List<Integer>> h = new LinkedList<>();
        //组装区间
        for (int i = 0; i < 26; i++) {
            //if (hash[i][0] != hash[i][1]) {
            temp.clear();
            temp.add(hash[i][0]);
            temp.add(hash[i][1]);
            //System.out.println(temp);
            h.add(new ArrayList<>(temp));
            // }
        }
        // System.out.println(h);
        // System.out.println(h.size());
        int[][] res = new int[h.size()][2];
        for (int i = 0; i < h.size(); i++) {
            List<Integer> list = h.get(i);
            res[i][0] =  list.get(0);
            res[i][1] =  list.get(1);
        }

        return res;

    }

    public  List<Integer> partitionLabels(String s) {
        int[][] partitions = findPartitions(s);
        List<Integer> res = new ArrayList<>();
        Arrays.sort(partitions, (o1, o2) -> Integer.compare(o1[0], o2[0]));
        int right = partitions[0][1];
        int left = 0;
        for (int i = 0; i < partitions.length; i++) {
            if (partitions[i][0] > right) {
                //左边界大于右边界即可纪委一次分割
                res.add(right - left + 1);
                left = partitions[i][0];
            }
            right = Math.max(right, partitions[i][1]);

        }
        //最右端
        res.add(right - left + 1);
        return res;

    }
}

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        hash = [0] * 26
        for i in range(len(s)):
            hash[ord(s[i]) - ord('a')] = i
        result = []
        left = 0
        right = 0
        for i in range(len(s)):
            right = max(right, hash[ord(s[i]) - ord('a')])
            if i == right:
                result.append(right - left + 1)
                left = i + 1
        return result

# 解法二（不相交区间法）
class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        # 记录每个字母出现的区间
        def getBord(s):
            hash = [[-float('inf')] * 2 for _ in range(26)]
            for i in range(len(s)):
                if hash[ord(s[i]) - ord('a')][0] == -float('inf'):
                    hash[ord(s[i]) - ord('a')][0] = i
                hash[ord(s[i]) - ord('a')][1] = i
            # 去除字符串中未出现的字母所占用区间
            hash_filter = []
            for item in hash:
                if item[0] != -float('inf'): hash_filter.append(item)
            return hash_filter

        # 得到无重叠区间题意中的输入样例格式：区间列表
        hash = getBord(s)
        # 按照左边界从小到大排序
        hash.sort(key= lambda x: x[0])
        res = []
        left = 0
        # 记录最大右边界
        right = hash[0][1]
        for i in range(len(hash)):
            # 一旦下一区间左边界大于当前右边界，即可认为出现分割点
            if hash[i][0] > right:
                res.append(right - left + 1)
                left = hash[i][0]
            # 实时更新最大右边界
            right = max(right, hash[i][1])
        # 最右侧区间（字符串长度为1时的特殊情况也包含于其中）
        res.append(right - left + 1)
        return res
        
# 解法三：区间合并法 （结合下一题 56. Merge Intervals 的写法）
class Solution: # 
    def partitionLabels(self, s: str) -> List[int]:
        aaa = list(set(s))
        #aaa.sort()
        bbb = list(s)
        ccc = []
        for i in reversed(bbb):
            ccc.append(i)
        intervals = []
        for i in range(len(aaa)):
            intervals.append([bbb.index(aaa[i]),len(bbb)-ccc.index(aaa[i])-1])
        # 先求出各个字母的存在区间，之后利用区间合并方法得出所有不相邻的最大区间。
        intervals.sort(key = lambda x:x[0])
        newinterval = []
        left, right = intervals[0][0], intervals[0][1]
        for i in range(1,len(intervals)):
            if intervals[i][0] in range(left, right+1):
                right = max(intervals[i][1],intervals[i-1][1],right)
                left = min(intervals[i-1][0],left)
            else: 
                newinterval.append(right-left+1)
                left = intervals[i][0]
                right = intervals[i][1]
        newinterval.append(right-left+1)
        return newinterval                

func partitionLabels(s string) []int {
    var res []int;
    var marks [26]int;
    size, left, right := len(s), 0, 0;
    for i := 0; i < size; i++ {
        marks[s[i] - 'a'] = i;
    }
    for i := 0; i < size; i++ {
        right = max(right, marks[s[i] - 'a']);
        if i == right {
            res = append(res, right - left + 1);
            left = i + 1;
        }
    }
    return res;
}

func max(a, b int) int {
    if a < b {
        a = b;
    }
    return a;
}

var partitionLabels = function(s) {
    let hash = {}
    for(let i = 0; i < s.length; i++) {
        hash[s[i]] = i
    }
    let result = []
    let left = 0
    let right = 0
    for(let i = 0; i < s.length; i++) {
        right = Math.max(right, hash[s[i]])
        if(right === i) {
            result.push(right - left + 1)
            left = i + 1
        }
    }
    return result
};

function partitionLabels(s: string): number[] {
    const length: number = s.length;
    const resArr: number[] = [];
    const helperMap: Map<string, number> = new Map();
    for (let i = 0; i < length; i++) {
        helperMap.set(s[i], i);
    }
    let left: number = 0;
    let right: number = 0;
    for (let i = 0; i < length; i++) {
        right = Math.max(helperMap.get(s[i])!, right);
        if (i === right) {
            resArr.push(i - left + 1);
            left = i + 1;
        }
    }
    return resArr;
};

object Solution {
  import scala.collection.mutable
  def partitionLabels(s: String): List[Int] = {
    var hash = new Array[Int](26)
    for (i <- s.indices) {
      hash(s(i) - 'a') = i
    }

    var res = mutable.ListBuffer[Int]()
    var (left, right) = (0, 0)
    for (i <- s.indices) {
      right = math.max(hash(s(i) - 'a'), right)
      if (i == right) {
        res.append(right - left + 1)
        left = i + 1
      }
    }

    res.toList
  }
}

use std::collections::HashMap;
impl Solution {
    fn max (a: usize, b: usize) -> usize {
        if a > b { a } else { b }
    }
    pub fn partition_labels(s: String) -> Vec<i32> {
        let s = s.chars().collect::<Vec<char>>();
        let mut hash: HashMap<char, usize> = HashMap::new();
        for i in 0..s.len() {
            hash.insert(s[i], i);
        }
        let mut result: Vec<i32> = Vec::new();
        let mut left: usize = 0;
        let mut right: usize = 0;
        for i in 0..s.len() {
            right = Self::max(right, hash[&s[i]]);
            if i == right {
                result.push((right - left + 1) as i32);
                left = i + 1;
            }
        }
        result
    }
}