Code Destine

Problem Statement

You have given a string S of lowercase letters, these letters form consecutive groups of the same character. For example, a string like S = “abbcccczyyy” has the groups “a”, “bb”, “cccc”, “z” and “yyy”. If a group has 3 or more characters, then this group is called as large group.

Write a program to find the start and end positions of every large group and return the result in lexicographic order.

Example 

Input :- "abbcccczyyy"
Output :- [3, 6]
[8, 10]

Input :- "abbcczzzzzyyyxxxx"
Output :- [5, 9]
[10, 12]
[13, 16]

Solution

To solve this problem, we can use Two pointer approach where one pointer start will always be at the start index of a group and another end pointer will always be at the end pointer of the same group.

Iterate the input string after converting it into a character array. At each iteration, check if the current character is equal to the previous character. If true, then move the end pointer towards the right position by 1 and if false, then save the start and end pointer in the list (if the difference between end and start pointer is greater than or equal to 3) and reset start pointer as a current index.

Program

import java.util.ArrayList;
import java.util.List;

public class Main {

	public static void main(String[] args) {		
		Main main = new Main();
		List<List<Integer>> result = main.largeGroupPositions("abbcczzzzzyyyxxxx");
		for(List<Integer> list : result) {
			System.out.println(list);		
		}				
	}
	
	/* Solution */    
	public List<List<Integer>> largeGroupPositions(String S) {
        
        List<List<Integer>> result = new ArrayList<>();
        
        char[] array = S.toCharArray();
        char previous = array[0];
        int start = 0, end = 0, count = 1;
        
        for(int i=1; i<array.length; i++){
            
            if(previous == array[i]){
                count++; 
                end = i;
            }else {                
                if(count >=3){
                    List<Integer> list = new ArrayList<>();
                    list.add(start);
                    list.add(end);
                    result.add(list);
                }                
                previous = array[i];
                start = i;
                count = 1;                
            }            
        }
        
        if(count >=3){
            List<Integer> list = new ArrayList<>();
            list.add(start);
            list.add(end);
            result.add(list);
        }        
        return result;
    }
}

Result

[5, 9]
[10, 12]
[13, 16]

Similar Post

1. Find the Duplicate Number in Array
2. Find Common Characters in Array of Strings
3. Duplicate Zeros in Array

That’s all for Positions of Large Groups in Java, If you liked it, please share your thoughts in a comments section and share it with others too.