划分字母区间

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型ArrayList
     */
    public ArrayList<Integer> splitString (String s) {
        // write code here
        Map<Character,Integer> map = new HashMap<>();
        ArrayList<Integer> res = new ArrayList<>();
        int end = -1;
        int start = 0;
        
        //存储每个字母最后的位置
        for(int i = 0 ;i<s.length();i++){
            map.put(s.charAt(i),i);
        }
        
        
        for(int i = 0;i<s.length();i++){
            end = Math.max(end,map.get(s.charAt(i)));
            if(end == i ){
                res.add(end - start + 1);
                start = i+1;
            }
        }
                           
        return res;
                
       
        
    }
}

package main

import _"fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @return int整型一维数组
*/
func splitString( s string ) []int {
    ends:=map[byte]int{}
    for i,ch:=range []byte(s){
        ends[ch]=i
    }
    ans:=[]int{}
    var l,r int
    for i:=0;i<len(s);i++{
        r=max(r,ends[s[i]])
        if i==r{
            ans=append(ans,r-l+1)
            l=i+1
        }
    }
    return ans
}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param s string字符串
# @return int整型一维数组
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/3a54a4f5bfa14891adb55484519210be?tpId=196&tqId=40445&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    参考：
        大神：牛客683289936号
    算法：
        本题要求对字符串进行尽可能多的划分，但是要求如果出现相同字符，那么该字符所包含的区间必须划分到一起，比如"abba", 划分后为[4]
        首次遍历字符串s：
            建立哈希表hashMap，键为s中的字符，值为该字符最后一次出现的下标
        再次遍历字符串s：
            使用start、end分别记录待截取区间的左右边界，其中end更新为包含重复元素的最远右边界
            当i与end相遇，就需要进行区间截取，同时更新start
    复杂度：
        时间复杂度：O(n), n为字符串s的长度
        空间复杂度：O(m), m为不重复的字符数量
    """

    def splitString(self, s):
        # write code here
        n, hashMap = len(s), {}

        for i in range(n): # 哈希表记录每个字符最后一次出现的下标
            hashMap[s[i]] = i
        # print hashMap

        start, end, res = 0, -1, []
        for i in range(n):
            end = max(end, hashMap[s[i]]) # end更新为包含重复元素的最远边界
            if i == end: # 访问到右边界，需要进行区间截取
                res.append(end - start + 1)
                start = i + 1
        return res


if __name__ == "__main__":
    sol = Solution()

    s = "anfjaklii"

    # s = "abba"

    # s = "abcabc"

    # s = "abcac"

    res = sol.splitString(s)

    print res