题解 | #划分字母区间#

import java.util.*;

/**
 * NC355 划分字母区间
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型ArrayList
     */
    public ArrayList<Integer> splitString (String s) {
        return solution1(s);
        // return solution2(s);
    }

    /**
     * Single HashMap
     * @param s
     * @return
     */
    private ArrayList<Integer> solution1(String s){
        HashMap<Character, Integer> rightMap = new HashMap<>();
        int len =  s.length();
        for(int i=0,j=len-1; i<len&&j>=0; i++,j--){
            if(!rightMap.keySet().contains(s.charAt(j))){
                rightMap.put(s.charAt(j), j);
            }
        }

        ArrayList<Integer> list = new ArrayList<Integer>();
        int left=0,right=0;
        char ch;
        for(int i=0; i<len; i++){
            ch = s.charAt(i);
            right = Math.max(right, rightMap.get(ch));
            if(i == right){
                list.add(right-left+1);
                left = i+1;
            }
        }

        return list;
    }

    /**
     * Double HashMap
     * @param s
     * @return
     */
    private ArrayList<Integer> solution2(String s){
        HashMap<Character, Integer> leftMap = new HashMap<>();
        HashMap<Character, Integer> rightMap = new HashMap<>();
        int len =  s.length();
        for(int i=0,j=len-1; i<len&&j>=0; i++,j--){
            if(!leftMap.keySet().contains(s.charAt(i))){
                leftMap.put(s.charAt(i), i);
            }
            if(!rightMap.keySet().contains(s.charAt(j))){
                rightMap.put(s.charAt(j), j);
            }
        }

        ArrayList<Integer> list = new ArrayList<Integer>();
        int left,right;
        HashSet<Character> set = new HashSet<>();
        char ch;
        for(int i=0; i<len; ){
            ch = s.charAt(i);
            if(!set.contains(ch)){
                set.add(ch);
                left = leftMap.get(ch);
                right = rightMap.get(ch);
                if(left == right){
                    list.add(1);
                }else{
                    for(int j=left+1; j<right; j++){
                        ch = s.charAt(j);
                        if(!set.contains(ch)){
                            set.add(ch);
                            right = Math.max(right, rightMap.get(ch));
                        }
                    }
                    list.add(right-left+1);
                }
                i = right+1;
            }else{
                i++;
            }
        }

        return list;
    }
}