首页 > itarticle > algorithm notes: leetcode#830 positions of large groups

algorithm notes: leetcode#830 positions of large groups

admin 11月 12, 2020 0

Problem

Solution

Initial thoughts

Python implementation

class :
    def largeGroupPositions(self, S):
        """
        :type S: str
        :rtype: List[List[int]]
        """
        start = 0
        end = 0
        ans = []
        for i in range(1, len(S)):
            if S[i] == S[i-1]:
                end = i
            else:
                if end - start >= 2:
                    ans.append([start, end])
                start = i
        if end - start >= 2:
                    ans.append([start, end])
        return ans

Java implementation

class  {
    public List<List<Integer>> largeGroupPositions(String S) {
        int start = 0;
        int end = 0;
        List<List<Integer>> ans = new ArrayList();
        for(int i = 1; i < S.length(); i++){
            if(S.charAt(i-1)==S.charAt(i)){
                end = i;
            }else{
                if(end-start>=2){
                    ans.add(Arrays.asList(new Integer[]{start, end}));
                }
                start = i;
            }
        }
        if(end-start>=2){
            ans.add(Arrays.asList(new Integer[]{start, end}));
        }
        return ans;
    }
}

Time complexity

O(n).

Space complexity

O(n).

Links

830. Positions of Large Groups
(中文版) 算法笔记: 力扣#830 较大分组的位置